Extract elements from a heap
显示 更早的评论
I am trying an assignment on Heaps i.e. how to extract elements and bubble them down:
% binary min-heap container
% let us assume the heap contains the following elements already and
% is in a consistent state
BinMinHeap = [];
BinMinHeap(1).pos = [3,3]; BinMinHeap(1).key = 1;
BinMinHeap(2).pos = [4,2]; BinMinHeap(2).key = 3;
BinMinHeap(3).pos = [3,2]; BinMinHeap(3).key = 2;
BinMinHeap(4).pos = [3,1]; BinMinHeap(4).key = 4;
BinMinHeap(5).pos = [4,3]; BinMinHeap(5).key = 5;
% extract the minimal element from the heap and store it in "ExtractedElement"
ExtractedElement = ...;
%make heap consistent again by first moving the bottom element
%to the top and then down the binary tree
consistent = false;
while ~consistent
...;
end
4 个评论
Jan
2016-11-2
What is your question?
Ken
2016-11-3
Now please explain, how "minimal" is measured. The minimal key, norm of pos, minimal x or y value or what?
What does "extracting" mean? Do you want to get the value or should the value be removed from the data?
Finally define "consistent". We cannot suggest a method without knowing, what this term means in your special case.
采纳的回答
James Tursa
2016-11-3
I am assuming you have a typo in your code above and are really starting with keys in sorted "consistent" order ... i.e., I assume you really have this to start with:
BinMinHeap(2).key = 2;
BinMinHeap(3).key = 3;
To extract the min from the heap, simply this:
ExtractedValue = BinMinHeap(1); % <-- extract the current minimum element
Then all you have to do is "bubble" the others up into their new spots. I.e., write some code to shift element 2 into element 1 spot, then element 3 into element 2 spot, etc. After the shifting is done delete the last element. You can do this using a loop, or using an all-at-once vectorized statement.
7 个评论
Ken
2016-11-3
编辑：James Tursa
2016-11-4
Ken
2016-11-4
Ken
2016-11-4
James Tursa
2016-11-4
编辑：James Tursa
2016-11-4
"make heap consistent again by first moving the bottom element to the top and then down the binary tree"
I have no idea why you would do it this way since it seems like the most inefficient way possible. (Also not sure why this is called a binary tree since I don't see any tree structure at all). But I will give you some corrections.
BinMinHeap(1)=BinMinHeap(5);
The above line hard-codes the last value index. Instead of doing it that way, make your code more robust to handle any current size. E.g.,
nheap = numel(BinMinHeap);
BinMinHeap(1) = BinMinHeap(nheap);
Then this line:
n==2;
The above line doesn't do anything. It is a logical comparison statement (the result of which is thrown away), not an assignment statement. Also it doesn't start at the right place. You want this instead:
n = 1;
Then your end condition:
if (n==5);
break;
end
Again, don't hard code the ending value, but use a calculated value. E.g.,
if (n==nheap);
break;
end
Once everything is done you need to lop off that last value from the array so it does not remain duplicated in the array. So at the very end of your code, outside the loop, add this statement:
BinMinHeap(nheap) = [];
Your consistent variable is not used for anything and is not needed.
Finally, your code only works if there are at least two elements in the heap so that the comparison between the n'th and (n+1)'th elements is valid. You should modify your code so that it doesn't bomb if there is only one element to start with. (HINT: You don't need to do that while loop at all if there is only one element in the heap to start with)
Ken
2016-11-4
编辑：James Tursa
2016-11-4
James Tursa
2016-11-4
编辑：James Tursa
2016-11-4
You missed this change:
n = 1; % <-- need to start comparisons at the top
Also, you need to move that BinMinHeap(nheap) = [] line out of the loop
Ken
2016-11-6
更多回答（0 个）
类别
在 帮助中心 和 File Exchange 中查找有关 Shifting and Sorting Matrices 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!
Translated by 
