Com S 311 Section B Introduction to the Design and Analysis of Algorithms
Lecture Two for Week 4
Xiaoqiu (See-ow-chew) Huang
Iowa State University
February 18, 2021
Maintaining the Heap Property
We call MAX-HEAPIFY on an array A and an index i when the binary trees rooted at LEFT(i) and RIGHT(i) are max-heaps, but A[i] may be smaller than its children.
MAX-HEAPIFY(A, i)
1 lt = LEFT(i)
2 rt = RIGHT(i)
3 if lt <= A.heap-size and A[lt] > A[i]
4 largest = lt
5 else largest = i
6 if rt <= A.heap-size and A[rt] > A[largest]
7 largest = rt
8 if largest != i
9 exchange A[i] with A[largest]
10 MAX-HEAPIFY(A, largest)
5 i = 1, A.heap-size = 11 /\
/\ /\ 45 35
/\ /\ /\/\ 40 25 20 30
/\ /\ /\/\ 15 10 5 20
45 /\ /\ /\
i=2 5
/\ /\
/\/\ 40 25 20 30
/\ /\ /\/\ 15 10 5 20
35
45 /\ /\ /\ 40 35
/\ /\ i=4/\/\
5 25 2030 /\ /\
/\/\ 15 10 5 20
45 /\ /\ /\ 40 35
/\ /\ /\/\ 15 25 20 30
/\ /\ /\/\ 5 10 5 20
i=8
The Running Time of MAX-HEAPIFY
The running time of MAX-HEAPIFY on a node of height h is O(h). The height of a n-element heap is ⌊lgn⌋. Thus, the running time of MAX-HEAPIFY on a heap of size n is O(lgn).
Building a Heap
Previously, we showed that the elements in the subarray A[(⌊n/2⌋ + 1)..n] are all leaf nodes of the tree, so each of these nodes is a 1-element heap.
The procedure BUILD-MAX-HEAP goes through the remaining nodes of the tree in a reverse order and runs MAX-HEAPIFY on each one.
BUILD-MAX-HEAP(A)
1 A.heap-size = A.length
2 for i = floor(A.length/2) downto 1
3 MAX-HEAPIFY(A, i)
/\ 20 10 /\ /\
/ \i=5/\ 15 25 50 35
/\ /\ /\/\ 50 40 55 45
15 n = 11, floor(11/2) = 5.
\ At the start of iteration with i = 5
/ /\
/\ 20 10 /\ /\
i=4/\/\ 15 55 50 35
/\ /\ /\/\ 50 40 25 45
15 n = 11, floor(11/2) = 5.
\ At the start of iteration with i = 4
/ /\
15 n = 11, floor(11/2) = 5.
\ At the start of iteration with i = 3
/ /\
/\
20 10 i = 3
/\ /\ /\/\ 50 55 50 35
/\ /\ /\/\ 15 40 25 45
/\ 20 i = 2 50 /\ /\
/\/\ 50 55 10 35
/\ /\ /\/\ 15 40 25 45
15 n = 11, floor(11/2) = 5.
\ At the start of iteration with i = 2
/ /\
i=1 15 n=11,floor(11/2)=5.
/ \ At the start of iteration with i = 1
/\ /\ 55 50
/\ /\ /\/\ 50 45 10 35
/\ /\ /\/\ 15 40 25 20
/\ 50 50 /\ /\
/\/\ 40 45 10 35
/\ /\ /\/\ 15 15 25 20
55 n = 11, floor(11/2) = 5.
\ At the end of the last iteration
/ /\
Proving the Correctness of BUILD-MAX-HEAP
We show that BUILD-MAX-HEAP is correct by using the following loop invariant:
At the start of each iteration of the for loop of lines 2-3, each of nodes i +1,i +2,…,n is the root of a max-heap.
Initialization: Before the first iteration of the loop, i = ⌊n/2⌋. each of nodes ⌊n/2⌋+1,⌊n/2⌋+2,…,n is a leaf node and is therefore the root of a 1-element max-heap.
Proving the Correctness of BUILD-MAX-HEAP
Maintenance: Assume that at the start of iteration i ≥ ⌊n/2⌋, each of nodes i +1,i +2,…,n is the root of a max-heap.
We want to show that at the end of this iteration, each of nodes i,i +1,i +2,…,n is the root of a max-heap. Decreasing i by 1 in the for loop counter update makes the loop invariant hold for the next iteration.
The children of node i are numbered higher than i. By the assumption, they are both roots of max-heaps. This meets the condition for MAX-HEAPIFY(A,i) to make node i the root of a max-heap. In addition, this call preserves the property that nodes i + 1, i + 2, …, n are all roots of max-heaps.
Termination: At termination, i = 0. By the loop invariant, each of nodes 1, 2, …, n is the root of a max-heap. So is node 1.
Bounding the Running Time of BUILD-MAX-HEAP
Previously, we showed that an n-element heap has height ⌊lg n⌋ and at most n/2h+1 nodes of any height h.
The number of iterations in the for loop of lines 2-3 is bounded by the number of nodes in the tree, which is also bounded by the sum of n/2h+1 over h from 0 to ⌊lg n⌋.
Bounding the Running Time of BUILD-MAX-HEAP
The running time of MAX-HEAPIFY on a node of height h is bounded by dh for a constant d > 0.
Thus, the running time of BUILD-MAX-HEAP is bounded from above by
⌊lgn⌋( n ×dh)≤⌊lgn⌋( n +1)×dh h=0 2h+1 h=0 2h+1
≤(dn/2)(⌊lgn⌋ h)+⌊lgn⌋dh h=0 2h h=0
≤ (dn/2)(∞ h ) + ⌊lg n⌋ dh h=0 2h h=0
≤ (dn/2) 1/2 + d(lg n)2 ≤ (dn/2)2 + dn = 2dn. (1−1/2)2
Thus, we can build a heap from an array in linear time.
Bounding the Running Time of BUILD-MAX-HEAP
In the above proof, we used the formula (A-8) in the textbook: ∞ kxk = x for|x|<1.
k =0 (1−x )2
By setting x = 1/2, we obtain
∞ h= 1/2 =2. h=0 2h (1−1/2)2
Heapsort
We design an algorithm called Heapsort by using BUILD-MAX-HEAP to build a max-heap on the array A[1..n] with n = A.length.
Then we exchange A[1] with A[n], decrease A.heap-size by 1, and call MAX-HEAPIFY(A, 1).
This process is repeated with A[1..n − 1].
HEAPSORT(A)
1 BUILD-MAX-HEAP(A)
2 for i = A.length downto 2
3 exchange A[1] with A[i]
4 A.heap-size = A.heap-size - 1
5 MAX-HEAPIFY(A, 1)
/\ 50 20
/\ /\ 40 45
55 n = 5, heap-size = 5
\ At the start of iteration with i = 5
/ /\
/ /
40
/\ 45 20
55
50 heap-size = 4
\ At the start of iteration with i = 4
/ /\
50
/\ 40 20
55
45 heap-size = 3
\ At the start of iteration with i = 3
/ /\
50
55
/ 20
/ /
40
heap-size = 2
At the start of iteration with i = 2
45
50
55
A: 20 40 45 50 55
Index 1 2 3 4 5
40
20
heap-size = 1
At the end of iteration with i = 2
45
Analyzing HEAPSORT
BUILD-MAX-HEAP takes time in O(n). The loop on lines 2-5 takes n − 1 iterations, each of which takes time in O(lg n).
Thus, HEAPSORT takes time in O(n lg n).