Extract elements from a heap
3 次查看(过去 30 天)
显示 更早的评论
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-3
编辑:Jan
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 个评论
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
更多回答(0 个)
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Loops and Conditional Statements 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!