Use of Position in Adaptable Priority Queue
.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty,.everyoneloves__bot-mid-leaderboard:empty{ height:90px;width:728px;box-sizing:border-box;
}
What is the use of Position in Adaptable priority queue(List based heap for keys) when we have to anyway pass the Entry reference to the functions remove(k), replaceKey(k).
i.e. If I have some reference "ref" to an entry in queue then I can simply call remove(ref) and replaceKey(ref) and that would still take O(1) time. Why would I need special position for this?
java data-structures
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
add a comment |
What is the use of Position in Adaptable priority queue(List based heap for keys) when we have to anyway pass the Entry reference to the functions remove(k), replaceKey(k).
i.e. If I have some reference "ref" to an entry in queue then I can simply call remove(ref) and replaceKey(ref) and that would still take O(1) time. Why would I need special position for this?
java data-structures
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
add a comment |
What is the use of Position in Adaptable priority queue(List based heap for keys) when we have to anyway pass the Entry reference to the functions remove(k), replaceKey(k).
i.e. If I have some reference "ref" to an entry in queue then I can simply call remove(ref) and replaceKey(ref) and that would still take O(1) time. Why would I need special position for this?
java data-structures
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
What is the use of Position in Adaptable priority queue(List based heap for keys) when we have to anyway pass the Entry reference to the functions remove(k), replaceKey(k).
i.e. If I have some reference "ref" to an entry in queue then I can simply call remove(ref) and replaceKey(ref) and that would still take O(1) time. Why would I need special position for this?
java data-structures
java data-structures
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
asked Nov 16 '18 at 19:47
rohit bhadoriarohit bhadoria
32
32
add a comment |
add a comment |
1 Answer
1
active
oldest
votes
It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently neally complete binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position i live at positions 2i + 1 and 2i+2. It's massively more efficient to find the ith element of an array than the ith element of a linked list.
For adaptable priority queues, The array(heaps) is a sequence of references to position instances, each of which stores a key, value, and the current index of the item within the array. The user will be given a reference to the Position instance for each inserted element.When we perform priority queue operations on our heap, and items are relocated
within our structure, we reposition the position instances within the array and we
update the third field of each position to reflect its new index within the array, and the update will take O(log(n)) time complexity.
answered Jan 9 at 13:47
minglyuminglyu
7613
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
StackExchange.using("externalEditor", function () {
StackExchange.using("snippets", function () {
StackExchange.snippets.init();
});
});
}, "code-snippets");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "1"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53344421%2fuse-of-position-in-adaptable-priority-queue%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently neally complete binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position i live at positions 2i + 1 and 2i+2. It's massively more efficient to find the ith element of an array than the ith element of a linked list.
For adaptable priority queues, The array(heaps) is a sequence of references to position instances, each of which stores a key, value, and the current index of the item within the array. The user will be given a reference to the Position instance for each inserted element.When we perform priority queue operations on our heap, and items are relocated
within our structure, we reposition the position instances within the array and we
update the third field of each position to reflect its new index within the array, and the update will take O(log(n)) time complexity.
answered Jan 9 at 13:47
minglyuminglyu
7613
add a comment |
It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently neally complete binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position i live at positions 2i + 1 and 2i+2. It's massively more efficient to find the ith element of an array than the ith element of a linked list.
For adaptable priority queues, The array(heaps) is a sequence of references to position instances, each of which stores a key, value, and the current index of the item within the array. The user will be given a reference to the Position instance for each inserted element.When we perform priority queue operations on our heap, and items are relocated
within our structure, we reposition the position instances within the array and we
update the third field of each position to reflect its new index within the array, and the update will take O(log(n)) time complexity.
answered Jan 9 at 13:47
minglyuminglyu
7613
add a comment |
It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently neally complete binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position i live at positions 2i + 1 and 2i+2. It's massively more efficient to find the ith element of an array than the ith element of a linked list.
For adaptable priority queues, The array(heaps) is a sequence of references to position instances, each of which stores a key, value, and the current index of the item within the array. The user will be given a reference to the Position instance for each inserted element.When we perform priority queue operations on our heap, and items are relocated
within our structure, we reposition the position instances within the array and we
update the third field of each position to reflect its new index within the array, and the update will take O(log(n)) time complexity.
answered Jan 9 at 13:47
minglyuminglyu
7613
It doesn't make any sense at all to implement a heap as a linked list. Heaps are inherently neally complete binary trees. You can store a heap in an array because it's easy to compute the array index of a node's children: the children of the node at position i live at positions 2i + 1 and 2i+2. It's massively more efficient to find the ith element of an array than the ith element of a linked list.
For adaptable priority queues, The array(heaps) is a sequence of references to position instances, each of which stores a key, value, and the current index of the item within the array. The user will be given a reference to the Position instance for each inserted element.When we perform priority queue operations on our heap, and items are relocated
within our structure, we reposition the position instances within the array and we
update the third field of each position to reflect its new index within the array, and the update will take O(log(n)) time complexity.
answered Jan 9 at 13:47
minglyuminglyu
7613
answered Jan 9 at 13:47
minglyuminglyu
7613
answered Jan 9 at 13:47
minglyuminglyu
7613
answered Jan 9 at 13:47
minglyuminglyu
7613
7613
add a comment |
add a comment |
Thanks for contributing an answer to Stack Overflow!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53344421%2fuse-of-position-in-adaptable-priority-queue%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
