Array Representation of Heaps A heap can be stored as an array A Root of tree is A 1 Left child of A i A 2i Right child of A i A 2i 1 Parent of A i A i 2 Heapsize A length A The elements in the subarray A n 2 1 n are leaves 1 BuildHeap Floyd s Method 12 5 11 3 10 6 9 4 8 1 7 2 Add elements arbitrarily to form a complete tree Pretend it s a heap and fix the heap order property 12 5 11 3 4 10 8 1 6 7 2 9 2 BuildHeap Floyd s Method 12 5 11 3 4 10 8 1 6 7 9 2 3 BuildHeap Floyd s Method 12 5 11 3 4 10 8 1 2 7 9 6 4 BuildHeap Floyd s Method 12 12 5 11 3 4 10 8 1 2 7 6 5 9 11 3 4 1 8 10 2 7 9 6 5 BuildHeap Floyd s Method 12 12 5 11 3 4 10 8 1 2 7 5 9 11 3 6 4 1 8 10 2 7 9 6 12 5 2 3 4 1 8 10 6 7 11 9 6 BuildHeap Floyd s Method 12 12 5 11 3 4 10 8 1 2 7 5 9 11 3 6 4 1 8 10 2 7 6 12 12 5 2 3 4 1 8 10 6 7 11 9 1 9 2 3 4 5 8 10 6 7 11 9 7 Finally 1 3 2 4 12 5 8 10 6 7 9 11 runtime 8 Heapify Heapify maintain the heap property Given a node i in the heap with children l and r Given two subtrees rooted at l and r assumed to be heaps Action let the value of the parent node float down so subtree at i satisfies the heap property If A i A l or A i A r swap A i with the largest of A l and A r Recurse on that subtree Running time O h h height of heap O lg n 9 01 14 19 Heaps To represent a heap as an array Parent i return i 2 Left i return 2 i right i return 2 i 1 10 01 14 19 Maintaining the Heap Property Assumptions Alg MAX HEAPIFY A i n Left and Right 1 l LEFT i subtrees of i are 2 r RIGHT i max heaps 3 if l n and A l A i A i may be 4 then largest l smaller than its 5 else largest i children 6 if r n and A r A largest 7 then largest r 8 if largest i 9 then exchange A i A largest 10 MAX HEAPIFY A largest n 11 Analysis of Heapify n 2h 1 1 where h is the height of the tree level 0 of the tree has 1 node level 1 has 2 nodes and up to level h which has 2h nodes All the leaves reside on level h 12 Analysis of Heapify At the bottommost level there are 2h nodes but we do not call Heapify on any of these so the work is 0 At the next to bottommost level there are 2h 1 nodes and each might sift down 1 level At the 3rd level from the bottom there are 2h 2 nodes and each might sift down 2 levels At level j from the bottom there are 2h j nodes and each might sift down j 1 levels 13 Analysis of Heapify 14 Analysis of Heapify 15 Heapify Example 16 4 10 14 2 7 8 9 1 A 16 4 10 14 7 David Luebke 3 16 9 3 2 8 1 01 14 19 Heapify Example 16 4 10 14 2 7 8 9 1 A 16 4 10 14 7 David Luebke 3 17 9 3 2 8 1 01 14 19 Heapify Example 16 4 10 14 2 7 8 9 1 A 16 4 10 14 7 David Luebke 3 18 9 3 2 8 1 01 14 19 Heapify Example 16 14 10 4 2 7 8 9 1 A 16 14 10 4 David Luebke 3 7 19 9 3 2 8 1 01 14 19 Heapify Example 16 14 10 4 2 7 8 9 1 A 16 14 10 4 David Luebke 3 7 20 9 3 2 8 1 01 14 19 Heapify Example 16 14 10 4 2 7 8 9 1 A 16 14 10 4 David Luebke 3 7 21 9 3 2 8 1 01 14 19 Heapify Example 16 14 10 8 2 7 4 9 1 A 16 14 10 8 David Luebke 3 7 22 9 3 2 4 1 01 14 19 Heapify Example 16 14 10 8 2 7 4 9 1 A 16 14 10 8 David Luebke 3 7 23 9 3 2 4 1 01 14 19 Heapify Example 16 14 10 8 2 7 4 9 1 A 16 14 10 8 David Luebke 3 7 24 9 3 2 4 1 01 14 19 Heapsort Given BuildHeap an in place sorting algorithm is easily constructed Maximum element is at A 1 Discard by swapping with element at A n Decrement heap size A A n now contains correct value Restore heap property at A 1 by calling Heapify Repeat always swapping A 1 for A heap size A 25 01 14 19 Heapsort Heapsort A BuildHeap A for i length A downto 2 Swap A 1 A i heap size A 1 Heapify A 1 26 01 14 19 Sample Run Start with unordered array of data Array representation 21 15 25 3 5 12 7 19 45 2 Binary tree representation 21 15 25 3 19 5 45 2 12 9 7 9 Sample Run Array elements 6 11 have no children Array representation 21 15 25 3 5 12 7 19 45 2 Binary tree representation 21 15 25 3 19 5 45 2 12 9 7 9 Sample Run Children of index 5 10 11 Array representation 21 15 25 3 5 12 7 19 45 2 Binary tree representation 21 15 25 3 19 5 45 2 12 9 7 9 Sample Run Children of index 5 10 11 put bigger of 5th 10th and 11th in 5th Array representation 21 15 25 3 5 12 7 19 45 2 Binary tree representation 21 15 25 3 19 5 45 2 12 9 7 9 Sample Run Children of index 5 10 11 put bigger of 5th 10th and 11th in 5th Array representation 21 15 25 3 9 12 7 19 45 2 Binary tree representation 21 15 25 3 19 9 45 2 12 5 7 5 Sample Run Children of index 4 8 9 put bigger of 4th 8th and 9th in 4th Array representation 21 15 25 3 9 12 7 19 45 2 Binary tree representation 21 15 25 3 19 9 45 2 12 5 7 5 Sample …
View Full Document
Unlocking...