Extract elements from a heap
3 Ansichten (letzte 30 Tage)
Ältere Kommentare anzeigen
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 Kommentare
Jan
am 3 Nov. 2016
Bearbeitet: Jan
am 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.
Akzeptierte Antwort
James Tursa
am 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 Kommentare
James Tursa
am 4 Nov. 2016
Bearbeitet: James Tursa
am 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
Weitere Antworten (0)
Siehe auch
Kategorien
Mehr zu Loops and Conditional Statements finden Sie in Help Center und File Exchange
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!