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

[Jan]

What is your question?

[Ken]

How to start extracting? i.e. do I form a blank array which I fill in from the heap elements that I extract? Thanks

[Jan]

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.

[Ken]

1. Minimal: Each entry is from a graph with x,y cords. The entry contains a key at that point. Minimal is the minimum of the key .e. the element with least key value goes on top. So, in the heap, the minimum-key is on top of the heap, then the next min is below it etc. 2. Extracting: the 5 heap elements are popped out from the heap one-by-one 3. Consistent: The elements in the heap are arranged in a way that the minimum key element is on top, next min. below it etc., so the max key element is at the bottom of the heap.

Thanks

Answer 1

[James Tursa]

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.

[Ken]

I tried this but get error "•BinMinHeap should at the end contain 4 elements" .

% extract the minimal element from the heap and store it in "ExtractedElement"

      ExtractedElement = BinMinHeap(1);

%make heap consistent again by first moving the bottom element
%to the top and then down the binary tree
BinMinHeap(1)=BinMinHeap(5);
consistent = false;
n==2;
while BinMinHeap(n).key>=BinMinHeap(n+1).key
                temp=BinMinHeap(n);
            BinMinHeap(n)=BinMinHeap(n+1);
            BinMinHeap(n+1)=temp;
        n=n+1;
        if (n==5);
            break;
                end

end

[Ken]

Tried the above in Matlab and get 4 elements in BinMinHeap, so puzzled as to why I get the above error.

[Ken]

Anyone care to help - now that Halloween is over!

[James Tursa]

"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]

Thanks James. Tried this and I get key =5 on top i.e BinMinHeap(1).key =5 followed by keys 2,3,4. However I think that this has to be bubbled down i.e. keys 2,3,4,5, so not sure how.

nheap = numel(BinMinHeap);
BinMinHeap(1) = BinMinHeap(nheap);
n = 2;
while BinMinHeap(n).key>=BinMinHeap(n+1).key
                temp=BinMinHeap(n);
            BinMinHeap(n)=BinMinHeap(n+1);
            BinMinHeap(n+1)=temp;
        n=n+1;
if (n==nheap);
            break;
end
BinMinHeap(nheap) = [];%tried putting this at the very end i.e 
%after last end but get error so put it here

end

[James Tursa]

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]

Thanks James, works fine.