Learning ObjectivesBy the end of this class, you should know...
![]()
Note that a Heap does not satisfy the conditions for a BST.
2.2. Max Heap PropertyA[Parent(i)] >= A[i] 2.3. Min Heap PropertyA[Parent(i)] <= A[i]
2.4. Additional Properties of Heaps
Verify that these properties are true using the diagram below:
2.5. Applications of Heaps
2.6. Important Heap Algorithms
3. Max-Heapify
3.2. Max-Heapify PseudoCodeMax-Heapify(A, i) l = left(i) //get the index of the left child of A[i] and store as l r = right(i) //get the index of the right child of A[i] and store r //Check if l is off the end of the array (heap) AND compare A[i] to its left child if (l <= Heap_size(A) AND A[l] > A[i]) index_of_max = l //update index_of_max if left is bigger //Check if r is off the end of the array (heap) AND compare A[r] to current max value if (r <= Heap_size(A) AND A[r] > A[index_of_max] index_of_max = r //update index_of_max if right is bigger if (i != index_of_max) //if A[i] was not bigger than its two children A[i]<--->A[index_of_max] //swap, so now A[i] stored at A[index_of_max] Max-Heapify(A, index_of_max) //recursively move through tree until restore heap property 3.3. Run-Time of Max-Heapify: O(height of the tree) = O(log n)4. Build-Heap
4.1. Build Heap Example4.2. Build-Heap PseudocodeBuild-Heap(A) n = Heap_size(A) for (i = floor(n/2) down to 1) //start at floor(n/2); we can ignore leaf nodes Max-Heapify(A, i) //call Max-Heapify helper function 4.3. Run-Time of Build-Heap: O(n) (surprise!)The intuition:
5. Build Heap PracticeTrace the build-heap algorithm on the given un-ordered arrays: |