CSC263 – Week 2, Lecture 2
Cristyn Howard Friday, January 19, 2018
• All heaps must satisfy the heap order property.
– in a MAX heap: values of children of node X are less than or equal to the value of node X
– in a MIN heap: values of children of node X are greater than or equal to the value of node X
• If there is one node (in a max heap) that violates the heap order property (i.e. it’s children are larger than it), recursively compare the value of node X to the value of it’s children and swap X with it’s largest child until the heap order property is restored.
• Max-Heapify(A,i): subprocedure used in INSERT and EXTRACT
– Inputs: array A, index in A
– Pre-condition: subtrees rooted at the left & right child of the node at i are heaps
– Post-condition: the subtree rooted at index i is a heap.
MaxHeapify(A,i):
L = LEFT(i), R = RIGHT(i);
if L ≤ heapsize(A) and A[l] > A[i]
largest = L else
– largest = i
if R ≤ heapsize(A) and A[r] > A[largest]
largest = R if largest ̸= i
swap(A[i],A[largest]) MaxHeapify(A,largest)
– Max-Heapify ∈ O(log n)
• Build-Max-Heap:
– First, store elements in an array representing a complete binary tree.
– Then, iterate from leaf to root performing MaxHeapify. Note that it is not necessary to perform MaxHeapify on leaf nodes, as they by definition preserve the heap order property and have no children to swap with. Because the last half of the nodes in an array are leaf nodes*, MaxHeapify is called starting from |A|.
2
– Build-Max-Heap(A): for i = |A| to 1, MaxHeapify(A,i). 2
– Intuitively, because Build-Max-Heap calls an O(log(n)) function n times, it would be in O(n log(n)), but it does not actually iterate through the whole height of the tree n times!
1
– Proof that Build-Max-Heap is ∈ O(n):
∗ each node at depth d has a height of at most h − d ∴ the heapification cost of each node is at
most h−d
∗ ∴ max heapification cost of each level = 2d(h − d)
∗ ∴ max heapification cost of the whole tree = h−1 2d(h − d) d=0
∗ seti=h−d,writeh 2h−ii=2hh i ≤(2h)inf i =(n)2
i=1 i=1 2i • Deleting from Binary Search Trees
i=1 2i
– Case A: X has no children
∗ set parent’s pointer to null, removed
– Case B: X has one child
∗ set parent’s pointer to X’s child, removed
– Case C: X has two children
∗ Successor(X): smallest node bigger than X, leftmost node in the right subtree of X ∗ set x to value of it’s successor, delete successor (reduces to case A or B)
2