Algorithm Analysis

and Design
(PMSCS 616)

Lecture 5
Divide and Conquer (Heapsort)
Special Types of Trees
Def: Full binary tree = a binary 4
tree in which each node is either a
1 3
leaf or has degree exactly 2.
1 1
2 9
6 0
1 1
8 7
4 2
Full binary tree

Def: Complete binary tree = A

4
complete binary tree is a binary
tree in which every level, except 1 3
possibly the last, is completely 1 1
2 9
filled, and all nodes are as far left 6 0
as possible. 1
2

Complete binary tree

Definitions
Height of a node = the number of edges on the longest simple path
from the node down to a leaf
Level of a node = the length of a path from the root to the node
Height of tree = height of root node

4 Height of root = 3

1 3
Height of (2)= 1 1 1
2 9 Level of (10)= 2
6 0
1
8
4
Useful Properties

height

height

4 Height of root = 3

1 3
Height of (2)= 1 1 1
2 9 Level of (10)= 2
6 0
1
8
4
Heaps
A complete binary tree
Each of the elements contains a value that is less than or equal to the value
of each of its children (Min-heap)
Each of the elements contains a value that is greater than or equal to the
value of each of its children (Max-heap)
Heaps
A complete binary tree
Each of the elements contains a value that is less than or equal to the value
of each of its children (Min-heap)
Each of the elements contains a value that is greater than or equal to the
value of each of its children (Max-heap)

1 11

2 5 9 4

3 4 8 7 7 8 3 1

11 6 9 2 5 6
Min-heap Max-heap
Heaps
A complete binary tree Shape property
Each of the elements contains a value that is less than or equal to the value
of each of its children (Min-heap)
Each of the elements contains a value that is greater than or equal to the
value of each of its children (Max-heap)

1 11

2 5 9 4

3 4 8 7 7 8 3 1

11 6 9 2 5 6
Min-heap Max-heap

• The shape of all heaps with a given number of elements is the same.
Heaps
A complete binary tree Shape property
Each of the elements contains a value that is less than or equal to the value
of each of its children (Min-heap)
Each of the elements contains a value that is greater than or equal to the
value of each of its children (Max-heap)

Heap 11
1
property/Order
property
2 5 9 4

3 4 8 7 7 8 3 1

11 6 9 2 5 6
Min-heap Max-heap

• The shape of all heaps with a given number of elements is the same.
• The root node always contains the largest value in the max-heap (in addition, the
subtrees are heaps as well).
Heaps (Implementation Issue)
Heap elements can be stored as array elements (since the tree is complete)

11

9 4

7 8 3 1

2 5 6
Heaps (Implementation Issue)
Heap elements can be stored as array elements (since the tree is complete, there
are not any “holes” in the tree)

11
Index Value

9 4 1 11
2 9
7 8 3 1 3 4
4 7
2 5 6 5 8
6 3
Map from array elements to tree nodes and vice versa
Root – A[1] 7 1
Left[i] – A[2i] 8 2
Right[i] – A[2i+1]
Parent[i] – A[⎣i/2⎦] 9 5
10 6
Heaps (Implementation Issue)
Heap elements can be stored as array elements (since the tree is complete, there
are not any “holes” in the tree)

11
Index Value

9 4 1 11
2 9
7 8 3 1 3 4
4 7
2 5 6 5 8
6 3
length[A] – number of elements in array A.
No. of leaves = ⎡n/2⎤
7 1
Height of a heap = ⎣lg n ⎦ 8 2
9 5
10 6
Operations on Heaps
Maintain/Restore the max-heap property
MAX-HEAPIFY

Create a max-heap from an unordered array

BUILD-MAX-HEAP

Sort an array in place

HEAPSORT

Priority queues
Maintaining the Heap Property
• Suppose a node is smaller than a child
• Assume Left and Right subtrees of i are max-heaps
• To eliminate the violation:
• Exchange with larger child
• Move down the tree
• Continue until node is not smaller than children
Example
MAX-HEAPIFY(A, 2, 10)

A[2] ↔ A[4]

A[2] violates the heap property A[4] violates the heap property

A[4] ↔ A[9]

Heap property restored

Heap Operations: Heapify()
Heapify(): maintain the heap property
• Given: a node i in the heap with children l and r
• Given: two subtrees rooted at l and r, assumed to be heaps
• Problem: The subtree rooted at i may violate the heap
property
• Action: let the value of the parent node “float down” so
subtree at i satisfies the heap property
• May lead to the subtree at the child not being a heap.
• Recursively fix the children until all of them satisfy the max-heap
property.
Illustration of Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11 4

7 9 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11 4

7 9 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

swap

11 4

7 9 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11

6 4

7 9 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

swap 11

6 4

7 9 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11

9 4

7 6 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11

9 4
swap

7 6 3 1

2 5 8
The Heapify operation
Suppose that, the order property is violated by the root node only
(not any other node, they are in place)
Repair the structure so that it becomes a heap again (called Heapify
operation), that is, move the element down from the root position
until it ends up in a position where the heap property is satisfied

11

9 4

7 8 3 1

2 5 6
Procedure MaxHeapify

MaxHeapify(A, i) Assumption:
Left(i) and Right(i)
1. l ← left(i) are max-heaps.
2. r ← right(i)
3. if l ≤ heap-size[A] and A[l] > A[i]
4. then largest ← l
5. else largest ← i
6. if r ≤ heap-size[A] and A[r] > A[largest]
7. then largest ← r
8. if largest≠ i
9. then exchange A[i] ↔ A[largest]
10. MaxHeapify(A, largest)
Procedure MaxHeapify

MaxHeapify(A, i)
1. l ← left(i)
2. r ← right(i) Time to fix node i
3. if l ≤ heap-size[A] and A[l] > A[i] and its children =
4. then largest ← l O(1)

5. else largest ← i PLUS

6. if r ≤ heap-size[A] and A[r] > A[largest]
7. then largest ← r
Time to fix the
8. if largest≠ i subtree rooted at
9. then exchange A[i] ↔ A[largest] one of i’s children =
10. MaxHeapify(A, largest) T(size of subree at
largest)
Running Time for MaxHeapify(A, i)

MaxHeapify takes O(hi) where hi is the height of the

node i where MaxHeapify is applied
If MaxHeapify is applied on the root node, then it will
take O(h) time where h is the height of the whole tree
which is O(lgn)
Converting an array to a Max-Heap

Use MaxHeapify to convert an array A into a max-heap.

How?
Call MaxHeapify on each element in a bottom-up
manner starting from the lowest parent (which is at
index ⎣n/2⎦). Why start at n/2?
Because elements A[n/2 + 1 … n] are all leaves of the tree

BuildMaxHeap(A)
1. heap-size[A] ← length[A]
2. for i ← ⎣length[A]/2⎦ downto 1
3. do MaxHeapify(A, i)
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

4
2 3

1 3
4 5 6 7
1 1
2 9
8 9 10 6 0
1
8 7
4
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1
1 3
3. do MaxHeapify(A, i) 4 5
1
6 7
1
2 9
8 9 10 6 0
1
8 7
4
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1
1 3
3. do MaxHeapify(A, i) 4 5
1
6 7
1
2 9
8 9 10 6 0
1
8 7
4
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1
1 3
3. do MaxHeapify(A, i) 4 5
1
6 7
1
2 9
8 9 10 6 0
1
8 7
4
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 14 16 9 10 2 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1
1 3
3. do MaxHeapify(A, i) 4
1
5
1
6 7
1
9
8 4 9 10 6 0
2 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 3 14 16 9 10 2 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1
1 3
3. do MaxHeapify(A, i) 4
1
5
1
6 7
1
9
8 4 9 10 6 0
2 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 10 14 16 9 3 2 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1
1
3. do MaxHeapify(A, i) 4 5 6 0 7
1 1
9 3
8 4 9 10 6
2 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 1 10 14 16 9 3 2 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1
1
3. do MaxHeapify(A, i) 4 5 6 0 7
1 1
9 3
8 4 9 10 6
2 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 16 10 14 1 9 3 2 8 7

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 6 5 6 0 7
1
1 9 3
8 4 9 10

2 8 7
Building a heap
1 2 3 4 5 6 7 8 9 10
4 16 10 14 7 9 3 2 8 1

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 6 5 6 0 7
1
7 9 3
8 4 9 10

2 8 1
Building a heap
1 2 3 4 5 6 7 8 9 10
4 16 10 14 7 9 3 2 8 1

BuildMaxHeap(A) 1

4
1. heap-size[A] ← length[A]
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 6 5 6 0 7
1
7 9 3
8 4 9 10

2 8 1
Building a heap
1 2 3 4 5 6 7 8 9 10
16 4 10 14 7 9 3 2 8 1

BuildMaxHeap(A) 1
1
1. heap-size[A] ← length[A] 6
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1
4
3. do MaxHeapify(A, i) 4 5 6 0 7
1
7 9 3
8 4 9 10

2 8 1
Building a heap
1 2 3 4 5 6 7 8 9 10
16 14 10 4 7 9 3 2 8 1

BuildMaxHeap(A) 1
1
1. heap-size[A] ← length[A] 6
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 4 5 6 0 7

8
4 9 10
7 9 3
2 8 1
Building a heap
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

BuildMaxHeap(A) 1
1
1. heap-size[A] ← length[A] 6
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 4 5 6 0 7

8
8 9 10
7 9 3
2 4 1
Building a heap
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

BuildMaxHeap(A) 1
1
1. heap-size[A] ← length[A] 6
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 4 5 6 0 7

8
8 9 10
7 9 3
2 4 1
Time complexity of Building a Heap
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

BuildMaxHeap(A) O(N) 1
1
1. heap-size[A] ← length[A] 6
2 3
2. for i ← ⎣length[A]/2⎦ downto 1 1 1
3. do MaxHeapify(A, i) 4 4 5 6 0 7

8
8 9 10
7 9 3
2 4 1
O(logN)
Time complexity: O(N logN) [Loose upper bound]
We can prove that it is O(N) [tighter upper bound]
 Build_Max_Heap(A)
Converts A[1…n] to a max heap

Build_Max_Heap(A)
: for i=n/2
downto 1
do Max_Heapify(A, i)

Why start at n/2?

Because elements A[n/2 + 1 … n] are all leaves of the

tree 2i > n, for i > n/2 + 1

Time=? O(n log n) via simple analysis

 Build_Max_Heap(A) Analysis
Converts A[1…n] to a max heap

Build_Max_Heap(A):
for i=n/2 downto 1
do Max_Heapify(A, i)

Observe however that Max_Heapify takes O(1) for time

for nodes that are one level above the leaves, and in
general, O(l) for the nodes that are l levels above the
leaves. We have n/4 nodes with level 1, n/8 with level 2,
and so on till we have one root node that is lg n levels
above the leaves.
 Build_Max_Heap(A) Analysis
Converts A[1…n] to a max heap

Build_Max_Heap(A)
: for i=n/2
downto 1
do Max_Heapify(A, i)
Total amount of work in the for loop can be summed
as: n/4 (1 c) + n/8 (2 c) + n/16 (3 c) + … + 1 (lg n
c)
Setting n/4 = 2k and simplifying we get:
c 2k( 1/20 + 2/21 + 3/22 + … (k+1)/2k ) The
term is brackets is bounded by a constant!
Running Time of BUILD MAX HEAP
• HEAPIFY takes O(h) ⇒ the cost of HEAPIFY on a node i is
proportional to the height of the node i in the tree

Height Level No. of nodes

h0 = 3 (⎣lgn⎦) i=0 20

h1 = 2 i=1 21

h2 = 1 i=2 22

h3 = 0 i = 3 (⎣lgn⎦) 23

hi = h – i height of the heap rooted at level i

ni = 2 i number of nodes at level i
Running Time of BUILD MAX HEAP
Cost of HEAPIFY at level i * number of nodes at that level

Replace the values of ni and hi computed before

Multiply by 2h both at the nominator and denominator and

write 2i as

Change variables: k = h - i

The sum above is smaller than the sum of all elements to ∞

and h = lgn

The sum above is smaller than 2

Running time of BUILD-MAX-HEAP: T(n) = O(n)

Heapsort
Goal:
Sort an array using heap representations

Idea:
Build a max-heap from the array
Swap the root (the maximum element) with the last element
in the array
“Discard” this last node by decreasing the heap size
Call MAX-HEAPIFY on the new root
Repeat this process until only one node remains
Heap Sort

HeapSort(A)
1. Build-Max-Heap(A)
2. for i ← length[A] downto 2
3. do exchange A[1] ↔ A[i]
4. heap-size[A] ← heap-size[A] – 1
5. MaxHeapify(A, 1)
Heap Sort
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

4
2 3

1 3
4 5 6 7
1 1
2 9
8 9 10 6 0
1
8 7
4
Heap Sort
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

1
HeapSort(A) 4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 3
4 5 6 7
3. do exchange A[1] ↔ A[i] 1 1
2 9
4. heap-size[A] ← heap-size[A] – 1 8 9 10 6 0
1
8 7
5. MaxHeapify(A, 1) 4
Heap Sort
1 2 3 4 5 6 7 8 9 10
4 1 3 2 16 9 10 14 8 7

1
HeapSort(A) 4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 3
4 5 6 7
3. do exchange A[1] ↔ A[i] 1 1
2 9
4. heap-size[A] ← heap-size[A] – 1 8 9 10 6 0
1
8 7
5. MaxHeapify(A, 1) 4
Heap Sort
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

1
HeapSort(A) 1
6
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 1
4 4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1
2 4 1
5. MaxHeapify(A, 1)
Heap Sort
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

1
HeapSort(A) 1
6
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 1
4 4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1
2 4 1
5. MaxHeapify(A, 1)
Heap Sort
1 2 3 4 5 6 7 8 9 10
16 14 10 8 7 9 3 2 4 1

1
HeapSort(A) 1
6
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 1
4 4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1
2 4 1
5. MaxHeapify(A, 1)

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
1 14 10 8 7 9 3 2 4 16

1
HeapSort(A) 1
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 1
4 4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 4
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
1 14 10 8 7 9 3 2 4 16

1
HeapSort(A) 1
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 1
4 4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 4
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
14 1 10 8 7 9 3 2 4 16

1
HeapSort(A) 1
4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1
1
4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
8 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 4
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
14 8 10 1 7 9 3 2 4 16

1
HeapSort(A) 1
4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1
8
4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
1 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 4
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
14 8 10 4 7 9 3 2 1 16

1
HeapSort(A) 1
4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1
8
4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 1
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
14 8 10 4 7 9 3 2 1 16

1
HeapSort(A) 1
4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1
8
4 5 6 0 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 9 3
4. heap-size[A] ← heap-size[A] – 1 1
2 1
5. MaxHeapify(A, 1) 6

i=10
Heap Sort
1 2 3 4 5 6 7 8 9 10
10 8 9 4 7 1 3 2 14 16

1
HeapSort(A) 1
0
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 8 9
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 1 3
4. heap-size[A] ← heap-size[A] – 1 1 1
2
5. MaxHeapify(A, 1) 4 6

i=9
Heap Sort
1 2 3 4 5 6 7 8 9 10
9 8 3 4 7 1 2 10 14 16

1
HeapSort(A) 9
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 8 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 1 2
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=8
Heap Sort
1 2 3 4 5 6 7 8 9 10
8 7 3 4 2 1 9 10 14 16

1
HeapSort(A) 8
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 7 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
2 1 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=7
Heap Sort
1 2 3 4 5 6 7 8 9 10
7 4 3 1 2 8 9 10 14 16

1
HeapSort(A) 7
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 4 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
1 9 10
2 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=6
Heap Sort
1 2 3 4 5 6 7 8 9 10
4 2 3 1 7 8 9 10 14 16

1
HeapSort(A) 4
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 2 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
1 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=5
Heap Sort
1 2 3 4 5 6 7 8 9 10
3 2 1 4 7 8 9 10 14 16

1
HeapSort(A) 3
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 2 1
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=4
Heap Sort
1 2 3 4 5 6 7 8 9 10
2 1 3 4 7 8 9 10 14 16

1
HeapSort(A) 2
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 1 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=3
Heap Sort
1 2 3 4 5 6 7 8 9 10
1 2 3 4 7 8 9 10 14 16

1
HeapSort(A) 1
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 2 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

i=2
Heap Sort
1 2 3 4 5 6 7 8 9 10
1 2 3 4 7 8 9 10 14 16

1
HeapSort(A) 1
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 2 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6
Heap Sort
1 2 3 4 5 6 7 8 9 10
1 2 3 4 7 8 9 10 14 16

HeapSort(A)
O(N) 1

1
1. Build-Max-Heap(A)
2 3
2. for i ← length[A] downto 2 2 3
4 5 6 7
3. do exchange A[1] ↔ A[i]
8
4 9 10
7 8 9
4. heap-size[A] ← heap-size[A] – 1 1 1 1
5. MaxHeapify(A, 1) 0 4 6

O(NlogN)
Time complexity: O(NlogN)
Priority Queues (PQ)
Properties:
• Each element is associated with a priority (key)
• The key with the highest (MAX-PQ)/lowest (MIN-PQ) key
is extracted first
• Can be implemented as a Max-Heap/Min-Heap

An application: Schedule jobs on a shared resource

•PQ keeps track of jobs and their relative priorities
•When a job is finished or interrupted, highest priority job is
selected from those pending using EXTRACT-MAX function
•A new job can be added at any time using INSERT function
 Applications of Priority Queue
Graph algorithms:
• Dijkstra’s and A*-search algorithms to compute
shortest paths
• Prim’s algorithm to compute minimum spanning
tree (MST) of a graph
Others:
• Huffman coding for compressing data
• Resource scheduling in operating systems