Max Heap and Priority Queues Part 1 Topics of this lecture The Heap Data Structure Heapify Build Heap Heapsort Max and ExtractMax IncreaseKey and Insertion Analysis of Heap Operations The Max Heap Data Structure Definition An array object with a tree view and heap property Tree view Tree view The n elements are stored in A 1 A 2 A n Can be viewed as a nearly complete binary tree the tree nodes in a complete binary tree are filled up one level at a time from left to right PARENT i return i 2 LEFT i RIGHT i return 2i return 2i 1 Heap property A parent i A i 2 i n The Max Heap Data Structure Definition For ease of presentation we will use the following equivalent Heap property in the textbook A parent i A i 2 i n heap property at node i A i A left i if left i n A i A right i if right i n We say heap property is violated at node i if one of the following happens left i n but A i A left i right i n but A i A right i The Max Heap Data Structure Example The following is a max heap with 10 elements 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example It has a tree view A nearly complete binary tree from A 1 to A 10 where 10 is the heap size 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 10 1 9 6 16 1 14 2 10 3 8 4 7 5 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example Clearly heap property is not violated at nodes 10 9 8 7 6 as none of them has a child node 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example We verify that heap property is not violated at node 5 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example We verify that heap property is not violated at node 4 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example We verify that heap property is not violated at node 3 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example We verify that heap property is not violated at node 2 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure Example We verify that heap property is not violated at node 1 Verified It is a max heap 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 4 1 10 16 1 14 2 10 3 8 4 7 5 9 6 3 7 2 8 4 9 1 10 11 12 The Max Heap Data Structure This is NOT a max heap The tree view is violated 1 16 3 10 6 9 7 3 2 14 5 7 10 1 2 8 4 8 4 8 4 8 2 9 11 16 1 14 2 10 3 7 5 9 6 3 7 4 9 1 11 10 12 The Max Heap Data Structure This is NOT a max heap Heap property is violated at node 5 not node 10 1 16 2 14 3 10 4 8 5 7 6 9 7 3 8 2 9 10 11 11 4 8 4 1 2 8 16 1 14 2 10 3 7 5 9 6 3 7 4 9 11 10 11 12 Summary The max heap data structure is an array object that has A nearly completely binary tree view Heap property It should be implemented as an array object not a binary tree Max Heap and Priority Queues Part 2 Topics of this lecture The Heap Data Structure Heapify Build Heap Heapsort Max and ExtractMax IncreaseKey and Insertion Analysis of Heap Operations Max Heapify largest i largest LEFT i r RIGHT i if heap size A and A A i then else if r heap size A and A r A largest then if largest i then MAX HEAPIFY A i O 1 T 2n 3 T n worst case running time of HEAPIFY A i on a heap with n elements is proportional to the height of the tree O log n Assumption LEFT i and RIGHT i are max heaps before the call exchange A i and A largest MAX HEAPIFY A largest largest r Example Max Heapify A 2 We illustrate the steps of max heapify A 2 1 16 i 2 4 3 10 4 14 5 7 6 9 7 3 8 2 9 8 10 1 9 6 16 1 4 2 10 14 7 3 5 4 3 7 2 8 8 9 1 10 11 12 Example Max Heapify A 2 The tree rooted at left i is a max heap 1 16 i 2 4 3 10 4 14 5 7 6 9 7 3 8 2 9 8 10 1 9 6 16 1 4 2 10 14 7 3 5 4 3 7 2 8 8 9 1 10 11 12 Example Max Heapify A 2 The tree rooted at right i is a max heap 1 16 i 2 4 3 10 4 14 5 7 6 9 7 3 8 2 9 8 10 1 9 6 16 1 4 2 10 14 7 3 5 4 3 7 2 8 8 9 1 10 11 12 Example Max Heapify A 2 We do not need to know whether the tree rooted at node i is a max heap or not In this particular case it is not 1 16 i 2 4 3 10 4 14 5 7 6 9 7 3 8 2 9 8 10 …
View Full Document
Unlocking...