Pop Quiz
2. Show that an n-element heap has height (lg n)
• Since the height of an n-element heap must satisfy that 2h £ n £ 2h+1-1 < 2h+1.
• Wehave h£lgn
5 else largest = i
6 if r ≤ A.heap-size and A[r] > A[largest]
Assumption:
Left(i) and Right(i) are max-heaps.
7
8
9 10
largest = r
if largest 1 i
exchange A[i] « A[largest] Max-Heapify(A, largest)
T (n) £ T ( 2n ) + Q(1) Þ T (n) = O(lg n) 3
Alternatively O(h) (h: height)
L6.5
Max-Heapify(A,2) heap-size[A] = 10
Max-Heapify(A,2)
-> Max-Heapify(A,4)
-> Max-Heapify(A,9)
L6.6
16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.7
16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.8
16
4 10
14 7 9 3 281
A=
16
4
10
14
7
9
3
2
8
1
L6.9
16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.10
16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.11
16
14 4793
281
A=
10
16
14
10
4
7
9
3
2
8
1
L6.12
16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.13
16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.14
16
14 8793
241
A=
10
16
14
10
8
7
9
3
2
4
1
L6.15
Running Time for Max-Heapify
Max-Heapify(A,i)
1 2 3 4 5 6 7 8 9
l = Left(i)
r = Right(i)
if l ≤ A.heap-size and A[l] > A[i]
largest = l else largest = i
if r ≤ A.heap-size and A[r] > A[largest] largest = r
if largest 1 i
exchange A[i] « A[largest]
10 Max-Heapify(A, largest)
Time to fix node i and its children = Q(1)
PLUS
Time to fix the subtree rooted at one of i’s children = T(size of subree at largest)
L6.16
Max-Heapify
-To make node i max heap
Max-Heapify(A,1)
1
23 4567
8 9 10 11 12 13 14 15
A=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
L6.17
Max-Heapify(A,1)
1
Largest =3
23 4567
8 9 10 11 12 13 14 15
A=
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
L6.18
Max-Heapify(A,largest) = Max-Heapify(A,3)
3 21 4567
8 9 10 11 12 13 14 15
A=
3
2
1
4
5
6
7
8
9
10
11
12
13
14
15
L6.19
Max-Heapify(A,3)
3 21 4567
Largest =7
8 9 10 11 12 13 14 15
A=
3
2
1
4
5
6
7
8
9
10
11
12
13
14
15
L6.20
Max-Heapify(A,7)
3 27 4561
Largest =7
8 9 10 11 12 13 14 15
A=
3
2
7
4
5
6
1
8
9
10
11
12
13
14
15
L6.21
Max-Heapify(A,7)
3 27 4561
Largest =15 8 9 10 11 12 13 14 15
3
2
7
4
5
6
1
8
9
10
11
12
13
14
15
A=
L6.22
Max-Heapify(A,15)
3 27
4 5 6 15
8 9 10 11 12 13 14 1
A=
3
2
7
4
5
6
15
8
9
10
11
12
13
14
1
L6.23
Running Time for Max-Heapify
Max-Heapify(A,i)
1 2 3 4 5 6 7 8 9
l = Left(i)
r = Right(i)
if l ≤ A.heap-size and A[l] > A[i]
largest = l else largest = i
if r ≤ A.heap-size and A[r] > A[largest] largest = r
if largest 1 i
exchange A[i] « A[largest]
10 Max-Heapify(A, largest)
Time to fix node i and its children = Q(1)
PLUS
Time to fix the subtree rooted at one of i’s children = T(size of subree at largest)
L6.24
Running Time for Max-Heapify(A, n)
• Fixing up relationships between i, l, and r takes Q(1)
time
• T(n) = T(largest) + Q(1)
• If the heap at i has n elements, how many elements can the subtrees at l or r have?
§ Draw it
• Answer: 2n/3 (worst case: bottom row 1/2 full)
• largest £ 2n/3 (worst case occurs when the last row of tree is exactly half full)
• So time taken by Max-Heapify() is given by T(n) £ T(2n/3) + Q(1)
L6.25
Why T(2n/3) ?
• The worst case: bottom row 1/2 full
• Number of nodes at –
• level 0 i.e. root is 20
• level 1 is 21
• level 2 is 22
• …
• level h is 2h
• Summation of all nodes from level 0 up to level h,
• S = 20 + 21 + 22 + … + 2h
• From geometric series summation rule we know that
• x0 + x1 + x2 + … + xn = (x n+1 – 1)/(x-1)
• Substituting x = 2, we get
• S = 2h+1 – 1. i.e. 2h+1 = S + 1
• As 2h+1 is the total nodes at level h+1, which means that the total number of leaf nodes (2h+1 ) is one node more than the total number of non-leaf nodes (S).
L6.26
Why T(2n/3) ?
Now let’s calculate the number of nodes in left subtree, right subtree and total ..
• Assume that number of non-leaf nodes in the left subtree of root = k.
• By the above reasoning, number of leaf nodes in the left subtree of root = k + 1. Number of non-leaf nodes in the right subtree of root = k as the tree is said to be exactly half full.
• Total number of nodes in the left subtree of root = k + k + 1 = 2k +1
• Total number of nodes in the tree, n = (2k + 1) + k + 1(root) = 3k + 2.
• Ratio of nodes in the left subtree and total nodes = (2k + 1) / (3k + 2) which is bounded above by 2/3.
• That’s the reason of saying that the children’s subtrees each have size at most 2n/3.
L6.27
Analyzing Heapify(): Formal
• So we have
T(n) £ T(2n/3) + Q(1)
• By case 2 of the Master Theorem, T(n) = O(lg n)
• Thus, Max-Heapify() takes logarithmic time
L6.28
6.3 Building a heap
• Use Max-Heapify to convert an array A into a max-heap.
• How?
• Call Max-Heapify on each element in a bottom-up manner.
Build-Max-Heap(A)
1. A.heap-size = A.length
2. for i = ëA.length / 2û downto 1 3. do Max-Heapify(A, i)
Why ëA.length / 2û ?
— the total number of nodes at leaf level is roughly the same as the total number of nodes without leaf level.
L6.29
Build-Max-Heap(A) heap-size[A] = 10
i=5 Max-Heapify(A, i)
i=4 Max-Heapify(A, i)
L6.30
i=3 i=2 Max-Heapify(A, i) Max-Heapify(A, i)
L6.31
i=1 Max-Heapify(A, i)
L6.32
Build-Max-Heap – Example Input Array:
24
21
23
22
36
29
30
34
28
27
Initial Heap: (not max-heap)
24
21
22 36 29 30
34
23
28 27
L6.33
Build-Max-Heap – Example
MaxHeapify(ë10/2û = 5) MaxHeapify(4) MaxHeapify(3) MaxHeapify(2) MaxHeapify(1)
23282424 2324
232464
32324641
2321617
3203
29
3203
248 271
L6.34
Running Time of Build-Max-Heap
• Loose upper bound:
§ Cost of a Max-Heapify call ́ No. of calls to Max-Heapify § O(lg n) ́ O(n) = O(nlg n)
• Tighter bound:
§ Cost of a call to Max-Heapify at a node depends on the
height, h, of the node – O(h).
§ Height of most nodes smaller than n.
§ Height of nodes h ranges from 0 to ëlg nû.
§ A heap of size, n, has at most no. of nodes with height h ? (6.3-3)
§is én/2h+1ù Why?
§ Answer will be posted on Canvas.
L6.35
lem 1
6.3-3
A heap of size n has at most dn/2h+1e nodes with height h. Key Observation: For
any n > 0, the number of leaves of nearly complete binary tree is dn/2e. Proof by
induction Base case: Show that it’s true for h = 0. This is the direct result from
above observation. Inductive step: Suppose it’s true for h 1. Let Nh be the
number of nodes at height h in the n-node tree T . Consider the tree T0 formed by
removingtheleavesofT. Ithasn0 =n dn/2e=bn/2cnodes. Notethatthe
nodesatheighthinTwouldbeatheighth 1intreeT0. LetN0 denotethe h 1
numberofnodesatheighth 1inT0,wehaveNh =N0 . Byinduction,wehave h 1
Nh =N0 =dn0/2he=dbn/2c/2hed(n/2)/2he=dn/2h+1e. h 1
Remark: Initially, I give following proof, which is flawed. The mistake is made in the
b
claim “The remaining nodes have height strictly more than h. To connect all subtrees
Running Time of Build-Max-Heap Tighter Bound for T(Build-Max-Heap)
T(Build-Max-Heap)
ëlgnû h å2h
h=0
£å¥h (!å¥kxk=x)
(1-x)2
= 1 / 2 , x = 1 / 2 in (A.8)
h=0 2h
k=0
(1-1/2)2 =2
ëlgnûé n ù åê2h+1 ú O(h)
h=0
ëlgnû
æåhö =Oçn 2h ÷
èh=0 ø
æëlgnûhö æ¥ hö Oçnå2h ÷=Oçnå2h ÷
èh=0 ø èh=0 ø = O(n)
Can build a heap from an unordered array in linear time
L6.37
6.4 Heapsort algorithm
• Sort by maintaining the as yet unsorted elements as a max-heap.
• Start by building a max-heap on all elements in A. § Maximum element is in the root, A[1].
• Move the maximum element to its correct final position.
§ Exchange A[1] with A[n].
• Discard A[n] – it is now sorted.
§ Decrement heap-size[A].
• Restore the max-heap property on A[1..n–1].
§ Call Max-Heapify(A, 1).
• Repeat until heap-size[A] is reduced to 2.
L6.38
Heapsort algorithm
Heapsort(A)
• Tosortanarrayinplace.
Heapsort(A)
1 Build-Max-Heap(A)
2 for i = A.length down to 2
3
4 5
exchange A[1]«A[i] A.heap-size = A.heap-size -1 Max-Heapify(A,1)
Heapsort Visualization 1
Heap Sort Dancing 2 Heapsort Visualization 3
Heapsort Visualization 4
L6.39
Heapsort(A)
{
} }
Heapsort
Build-Max-Heap(A);
for (i = length(A) downto 2)
{
Swap(A[1], A[i]);
heap_size(A) -= 1;
Max-Heapify(A, 1);
L6.40
Operation of Heapsort
L6.41
Analysis: O(n lg n)
L6.42
Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
L6.43
Algorithm Analysis
Heapsort(A)
1 Build-Max-Heap(A)
2 for i = A.length down to 2
3
4 5
exchange A[1]«A[i] A.heap-size = A.heap-size -1 Max-Heapify(A,1)
• In-place: no need additional space for sorting.
• Not Stable: do not maintain the relative location/order
of records with equal keys.
• Build-Max-Heap takes O(n) and each of the n-1 calls
to Max-Heapify takes time O(lg n). • Therefore, T(n) = O(n lg n)
L6.44
Heap Procedures for Sorting
• Max-Heapify
• Build-Max-Heap • HeapSort
O(lg n) O(n)
O(n lg n)
L6.45
Analyzing Heapsort
• The call to Build-Max-Heap() takes O(n) time
• Each of the n – 1 calls to Max-heapify() takes
O(lg n) time
• Thus the total time taken by HeapSort()
= O(n) + (n – 1) O(lg n) = O(n) + O(n lg n)
= O(n lg n)
L6.46
6.5 Priority Queues
• Popular & important application of heaps.
• Max and min priority queues.
• Maintains a dynamic set S of elements.
• Each set element has a key – an associated value.
• Goal is to support insertion and extraction efficiently. • Applications:
§ Ready list of processes in operating systems by their priorities – the list is highly dynamic
§ In event-driven simulators to maintain the list of events to be simulated in order of their time of occurrence.
L6.47
Priority Queues
• Heapsort is a nice algorithm, but in practice Quicksort (coming up) usually wins
• But the heap data structure is incredibly useful for implementing priority queues
§ A data structure for maintaining a set S of elements, each with an associated value or key
§ Supports the operations Insert(), Maximum(), and ExtractMax()
§ What might a priority queue be useful for?
L6.48
Priority Queues
• A max-priority queue support the following operations:
Insert(S, x) O(lg n) inserts the element x into the set S.
Maximum(S) O(1) returns the element of S with the largest key.
Extract-Max(S) O(lg n)
removes and returns the element of S with the largest
key.
Increase-Key(S,x,k) O(lg n)
increases the value of element x’s key to the new
value k, where k 3 x’s current key value
L6.49
Heap-Maximum
Heap-Maximum(A) 1 return A[1]
L6.50
Heap_Extract-Max
Heap_Extract-Max(A)
1 if A.heap-size < 1
2 error “heap underflow”
3 max = A[1]
4 A[1]= A[A.heap-size]
5 A.heap-size = A.heap-size - 1 6 Max-Heapify(A, 1)
7 return max
Running time : Dominated by the running time of Max-Heapify = O(lg n)
L6.51
Heap-Increase-Key
Heap-Increase-Key (A, i, key)
1 ifkey 1 and A[Parent(i)] < A[i] 5 exchange A[i] « A[Parent(i)] 6 i = Parent(i)
L6.52
Heap-Increase-Key(A,i,15)
L6.53
Heap-Increase-Key(A, i, key)
Heap-Increase-Key(A, i, key)
1 2 3 4 5 6
If key < A[i]
error “new key is smaller than the current key”
A[i] = key
while i > 1 and A[Parent[i]] < A[i]
exchange A[i] « A[Parent[i]] i = Parent[i]
Heap-Insert(A, key)
1 A.heap-size = heap-size[A] + 1
2 A[A.heap-size] = –¥
3 Heap-Increase-Key(A, A.heap-size, key)
L6.54
Examples
L6.55