CS计算机代考程序代写 algorithm Com S 311 Section B Introduction to the Design and Analysis of Algorithms

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).