MATLAB: Extract elements from a heap

bubbleheap

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

Best Answer

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.
Related Question