Initializing A Max Heap input array = [-, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
8 4 7 6 7 8 9 3 7 10 1 11 5 2
Initializing A Max Heap Start at rightmost array position that has a child.
8 4 7 6 7 8 9 3 7 10 1 11 5 2 Index is n/2.
Initializing A Max Heap Move to next lower array position.
8 4 7 6 7 8 9 3 7 10 1 5 11 2
Initializing A Max Heap
8 4 7 6 7 8 9 3 7 10 1 5 11 2
Initializing A Max Heap
8 9 7 6 7 8 4 3 7 10 1 5 11 2
Initializing A Max Heap
8 9 7 6 7 8 4 3 7 10 1 5 11 2
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 10 1 5 11 2
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 10 1 5 11 2
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 10 1 5 11 Find a home for 2.
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 5 1 11 Find a home for 2. 10
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 2 1 11 Done, move to next lower array position. 10 5
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 2 1 11 10 5 Find home for 1.
Initializing A Max Heap
11 8 9 7 6 3 8 4 7 7 2 10 5 Find home for 1.
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 2 11 10 5 Find home for 1.
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 2 11 10 5 Find home for 1.
Initializing A Max Heap
8 9 7 6 3 8 4 7 7 2 11 10 5 Done. 1
Time Complexity
8 7 6 3 4 7 7 10 11 5 2 9 8 1 Height of heap = h.
Number of subtrees with root at level j is <= 2 j-1.
Time for each subtree is O(h-j+1).
Complexity
Time for level j subtrees is <= 2j-1(h-j+1) = t(j).
Total time is t(1) + t(2) + … + t(h-1) =
Leftist Tree Linked binary tree.
Can do everything a heap can do and in the same asymptotic complexity.
Can meld two leftist tree priority queues in O(log n) time.
Extended Binary Trees Start with any binary tree and add an external node wherever there is an empty subtree.
Result is an extended binary tree.
Author:
Preferred Customer
Description:
Initializing A Max Heap8 9 7 6 3 8 4 7 7 2 1 11 10 5 Find home for 1.
Tags:
tree | the | leftist | min | root | and | subtree | meld
Created:
6/17/1995 11:31:02 PM
>
Share this presentation
|
Copy the following code to your webpage or blog to embed this presentation:
<a href="http://www.slidefinder.net/i/initializing_max_heap/33006000" class="slidefinder">chap9-2</a>
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
<a href="http://www.slidefinder.net/i/initializing_max_heap/33006000" class="slidefinder">chap9-2</a>
Det3
<script type="text/javascript" src="http://www.slidefinder.net/scripts/embedded.js"></script>
Share this presentation:
Comments