Heaps 2 5 9 2010 Goodrich Tamassia Heaps 6 7 1 Definition of a heap A heap is a tree that satisfies the heap property Minimum Heap Property The value stored at each node is less than or equal to the values stored at its children OR Maximum Heap Property for greater 01 15 19 Heap 2 Heap Structure Property All levels but the last leaf are full and the leaf nodes are left oriented i e filled from left to right Examples 3 Heap Order Property Heap order property For every non root node X the value in the parent of X is less than or equal to the value in X 10 10 20 30 20 80 15 40 50 80 60 85 99 700 not a heap 4 HEAPS Example of a 4 heap 5 d Heap 1 4 11 7 5 3 2 10 13 15 6 9 An example of 3heap 8 17 9 Definition of a heap A heap That has D children is called D Heap The most popular heap is 2 Heap Also called binary Heap Tree 01 15 19 Heap 7 Definition of a heap Difference between Binary Search Tree and Binary Heap Tree 01 15 19 Heap 8 Heap or Not a Heap Height of a Heap Theorem A heap storing n keys has height O log n Proof we apply the complete binary tree property Let h be the height of a heap storing n keys Since there are 2i keys at depth i 0 h 1 and at least one key at depth h we have n 1 2 4 2h 1 1 Thus n 2h i e h log n depth keys 0 1 1 2 h 1 2h 1 h 1 2010 Goodrich Tamassia Heaps 10 Operations on Heap Insert Delete Min 01 15 19 Heap 11 Percolating Up Heap Insert Example Insert 14 14 hole 12 Percolating Up Heap Insert Example 1 14 vs 31 Insert 14 14 14 hole 13 Percolating Up Heap Insert Example 1 14 vs 31 Insert 14 14 14 hole 2 14 vs 21 14 14 Percolating Up Heap Insert Example 1 14 vs 31 Insert 14 14 hole 2 14 vs 21 14 3 14 vs 13 Heap order prop Structure prop Path of percolation up 15 Heap DeleteMin Minimum element is always at the root Heap decreases by one in size Move last element into hole at root Percolate down while heap order property not satisfied 16 Percolating down Heap DeleteMin Example Make this position empty 17 Percolating down Heap DeleteMin Example Copy 31 temporarily here and move it down Make this position empty Is 31 min 14 16 Yes swap 31 with min 14 16 18 Percolating down Heap DeleteMin Example 31 Is 31 min 19 21 Yes swap 31 with min 19 21 19 Percolating down Heap DeleteMin Example 31 31 Is 31 min 19 21 Yes swap 31 with min 19 21 Is 31 min 65 26 Yes swap 31 with min 65 26 Percolating down 20 Percolating down Heap DeleteMin Example 31 Percolating down 21 Percolating down Heap DeleteMin Example 31 Heap order prop Structure prop 22 Basic Heap Operations 13 Example 21 24 65 16 31 1 9 26 32 Original Tree Insert 14 68 Basic Heap Operations 13 13 21 24 65 21 16 31 26 32 1 9 24 68 65 16 31 26 32 1 9 68 Basic Heap Operations 13 13 21 24 65 16 31 26 32 1 9 21 24 68 65 26 32 16 1 9 31 68 Basic Heap Operations 13 13 21 24 65 26 32 16 1 9 31 16 24 68 65 26 32 21 1 9 31 68 Basic Heap Operations 13 13 16 24 65 21 26 32 1 9 31 16 14 24 68 65 26 32 21 1 9 31 68 Basic Heap Operations 13 Example 65 16 14 19 21 26 32 Delete the minimum key 1 9 31 Original Tree 68 Basic Heap Operations 13 16 14 19 65 26 32 21 1 9 31 16 14 19 68 65 26 32 21 1 9 31 68 Basic Heap Operations 14 16 14 19 65 26 32 21 1 9 31 16 19 68 65 26 32 21 1 9 31 68 Basic Heap Operations 14 14 16 19 65 26 32 21 1 9 31 16 19 21 68 65 26 32 1 9 31 68 Basic Heap Operations 14 14 16 19 21 65 26 32 1 9 31 16 19 68 21 26 65 32 1 9 31 68 Basic Heap Operations 14 14 16 19 26 65 21 32 1 9 31 16 19 68 26 65 31 32 21 1 9 68 What are Heaps Useful For To implement priority queues Priority queue a queue where all elements have a priority associated with them Remove in a priority queue removes the element with the smallest priority insert removeMin 01 15 19 Heap 34 What are Heaps Useful For A stack is first in last out A queue is first in first out A priority queue is least first out The smallest element is the first one removed The definition of smallest is up to the programmer for example you might define it by implementing Comparator or Comparable If there are several smallest elements the implementer must decide which to remove first Remove any smallest element don t care which Remove the first one added 01 15 19 Heap 35 Heap Implementation o PQ A priority queue can be implemented as a heap In order to do this we have to define the heap property In Heapsort a node has the heap property if it is at least as large as its children For a priority queue we will define a node to have the heap property if it is as least as small as its children since we are using smaller numbers to represent higher priorities 12 3 Heapsort Blue node has the heap property 01 15 19 Heap 36 Heaps and Priority Queues We can use a heap to implement a priority queue We store a key element item at each internal node We keep track of the position of the last node 2 Sue 5 Pat 9 Jeff 2010 Goodrich Tamassia 6 Mark 7 Anna Heaps 37
View Full Document
Unlocking...