Extract elements from a heap
3 views (last 30 days)
Show older comments
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 Comments
Jan
on 3 Nov 2016
Edited: Jan
on 3 Nov 2016
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.
Accepted Answer
James Tursa
on 3 Nov 2016
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 Comments
James Tursa
on 4 Nov 2016
Edited: James Tursa
on 4 Nov 2016
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
More Answers (0)
See Also
Categories
Find more on Loops and Conditional Statements in Help Center and File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!