Introduction to

Algorithm Design and Analysis

[05] HeapSort

Jingwei Xu
http://cs.nju.edu.cn/ics/people/jingweixu
Institute of Computer Software
Nanjing University
In the last class …
• The sorting problem
• Assumptions
• InsertionSort
• Design
• Analysis: inverse
• QuickSort
• Design
• Analysis
HeapSort
• Heap
• HeapSort

• FixHeap
• ConstructHeap

• Complexity of HeapSort
• Accelerated HeapSort
How HeapSort Works
Elements to
Elements sorted
be sorted
Priority
Queue

Implementations

Fibonacci Binomial
Heap
Heap Heap
Elementary
Priority Queue ADT
• “FIFO” in some special sense. The “ rst” means some kind of
“priority”, such as value (largest or smallest)
• PriorityQ create()
• Precondition: none
• Postconditions: If pq=create(), then, pq refers to a newly created object and
isEmpty(pt)=true
• boolean isEmpty(PriorityQ pq)
• precondition: none
**pq can always be
• int getMax(PriorityQ pq) thought as a sequence
• precondition: isEmpty(pq)=false
• postconditions: ** of pairs (idi, wi), in
• void insert(PriorityQ pq, int id, oat w) non-decreasing order
• preconditions: none of wi
• postconditions: isEmpty(pq)=false; **
• void delete(PriorityQ pq)
• precondition: isEmpty(pq)=false
• postconditions: value of isEmpty(pq) updated; **
• void increaseKey(PriorityQ pq, int id, oat newKey)
fl
fi
fl
Heap: an Implementation of
Priority Queue
• A binary tree T is a heap structure if:
• T is complete at least though depth h-1
• All leaves are at depth h or h-1
• All path to a leaf of depth h are to the left of all path to
a leaf of depth h-1

• Partial order tree property

• A tree T is a (maximizing) partial order tree if and only if
the key at any node is greater than or equal to the
keys at each of its children (if it has any).
Heap: Examples
The maximal key is
always with the root

50
9

24 30

5 7
20 21 18 3

12 5 6
1 4 3 6
Heap: an Implementation of
Priority Queue
Heap
structure

Heap
Partial
order
property
HeapSort: the Strategy
heapSort(E, n)
Construct H from E, the set of n elements to be sorted;
for (i = n; i ≥ 1; i -=1){
curMax = getMax(H);
deleteMax(H);
E[i] = curMax;
}

deleteMax(H)
copy the rightmost element on the lowest level of H into K;
Delete the rightmost element on the lowest level of H;
xHeap(H, K);
fi
FixHeap
• Input: A nonempty binary tree H with a “vacant” root and its
two subtrees in partial order. An element K to be inserted.

• Output: H with K inserted and satisfying the partial order

tree property.
One comparison:
largerSubHeap is left- or right-
• Procedure: Subtree(H), the one with larger key at
xheap(H, K) its root.
if(H is a leaf) insert K in root(H); Special case: rightSubtree is empty.
else
set largerSubHeap;
if(K.key≥root(largerSubHeap).key) insert K in root(H);
else
Insert root(largerSubHeap) in root(H);
xHeap(largerSubHeap, K);
“Vacant” moving down
return;
fi
fi
FixHeap: an Example
Vacant
50

24 30 24 30

20 21 18 3 20 21 18 3

12 5 6 12 5
K=6

30 30

24 24 18

20 21 18 3 20 21 3

12 5 12 5
K=6 K=6
Worst Case Analysis for
xHeap
• 2 comparisons at most in one activation of the procedure
• The tree height decreases by one in the recursive call
• So, 2h comparisons are needed in the worst case, where h is the height of the tree
• Procedure: One comparison:
largerSubHeap is left- or right-
xheap(H, K) Subtree(H), the one with larger key at
if(H is a leaf) insert K in root(H); its root.
else Special case: rightSubtree is empty.
set largerSubHeap;
if(K.key≥root(largerSubHeap).key) insert K in root(H);
else
recursion
Insert root(largerSubHeap) in root(H);
xHeap(largerSubHeap, K);
“Vacant” moving down
return;
fi
fi
fi
Heap Construction
• Note: if left subtree and right subtree both
satisfy the partial order tree property, then
xHeap(H, root(H)) gets the thing done.
root

• We begin from a Heap Structure H:

void constructHeap(H) Post-order Traversal
if(H is not a leaf)
constructHeap(left subtree of H);
constructHeap(right subtree of H);
Element K = root(H);
xHeap(H, K);
return; left right
fi
fi
Correctness of
constructHeap
• Speci cation
• Input: A heap structure H, not necessarily
having the partial order tree property.
• Output: H with the same nodes rearranged to
satisfy the partial order tree property.
void constructHeap(H) H is a leaf: base case, satis ed trivially.
if(H is not a leaf)
constructHeap(left subtree of H);
constructHeap(right subtree of H);
Element K = root(H); Preconditions hold respectively?
xHeap(H, K);
return; Postcondition of constructHeap satis ed?
fi
fi
fi
fi
Linear Time Heap
Construction!
• The recursion equation:
W(n) = W(n − r − 1) + W(r) + 2 log n
• A special case: H is a complete binary tree:
• The size N=2d-1,
(then, for arbitrary n, N/2<n<N≤2n, so W(n)≤W(N)≤W(2n))
• Note: W(N) = 2W((N − 1)/2) + 2 log N
• The Master Theorem applies, with b=c=2, and the
critical exponent E=1, f(N) = 2 log N
2 log N 2 log N 2N ϵ
• Note: lim
N→∞ N 1−ϵ
= lim
N→∞ N 1−ϵ log 2
= lim
N→∞ ((1 − ϵ)log 2)N

• When 0<ε<1, this limit is equal to zero

E−ϵ
• So, 2 log N ∈ O(N ) , case 1 satis ed, we have W(n) ∈ Θ(N)
fi
Direct Analysis of Heap
construction
• Heap construction ⌊log n⌋
O(h)
∑ 2
cost = n h+1 = O(n)
• From recursion to iteration h=0

• Sum of row sums c = logn x; h = logn; # = 1

c = 2 x; h = 2; # = n/8
c = 1 x; h = 1; # = n/4
c = 0 x; h = 0; # = n/2
1 x = 2 comparisons
fi
fi
fi
fi
fi
Understanding the Heap
• Where is the kth element in the heap?

• 1st? 2nd? 3rd?

• kth? at what cost?

• Sum of heights
• At most n-1
• When the sum reaches n-1?
Implementing Heap
Using Array
9
50

5 7 24 30

20 21 18 3

1 4 3 6

9 5 7 1 4 3 6 12 5 6

50 24 30 20 21 18 3 12 5 6
Looking for the
Children Quickly
Starting from 1, not zero, then 50
the j th level has 2j-1 elements,
and there are 2j-1-1 elements in
24 30
the proceeding j-1 levels
altogether.
20 21 18 3
So, if E[i] is the kth
element at level j, then
i=(2j-1-1)+k, and the 12 5 6
index of its left child (if
existing) is
50 24 30 20 21 18 3 12 5 6
i+(2j-1-k)+2(k-1)+1=2i
The number of node on The number of children of the
the right of E[i] on level j nodes on level j on the left of E[i]
HeapSort: In-Space
Implementation
Heap
implemented as
a array (initial)

E[1]: The largest key E[n]->K: removed

to be moved to E[n] to be inserted

E[1]: The largest key in E[heapsize]->K:

current heap, to be removed to be inserted
moved to E[heapsize]
Current heap: processed by xHeap
fi
FixHeap: Using Array
• void xHeap(Element[ ] E, int heapSize, int root, Element K)
• int left = 2 * root; right = 2 * root + 1;
• if(left > heapSize) E[root] = K; // root is a leaf.
• else
• int largerSubHeap; // right or left to lter down.
• if(left == heapSize) largerSubHeap = left; // no right SubHeap;
• else if(E[left].key > E[right].key) largerSubHeap = left;
• else largerSubHeap = right;
• if(K.key ≥ E[largerSubHeap].key) E[root] = K;
• else E[root] = E[largerSubHeap]; // vacant ltering down one level.
• xHeap(E, heapSize, largerSubHeap, K);
• return;
fi
fi
fi
fi
HeapSort: the Algorithm
• Input: E, an unsorted array with n (>0)
elements, indexed from 1
• Sorted E, in non-decreasing order
“array version”
• Procedure:
void heapSort(Element[ ] E, int n)
int heapsize;
constructHeap(E, n, root);
for(heapsize = n; heapsize ≥ 2; heapsize -= 1)
Element curMax = E[1];
Element K = E[heapsize];
xHeap(E, heapsize - 1, 1, K);
E[heapsize] = curMax;
return;
fi
Worst Case Analysis
of HeapSort
n−1
• We have: W(n) = Wcons(n) +
∑
Wfix(k)
k=1
• It has been shown that:
Wcons(n) ∈ Θ(n) and Wfix(k) ≤ 2 log k
• Recall that:
n−1 n

∑ ∫1
2 ⌈log k⌉ ≤ 2 log e ln xdx = 2 log e(n ln n − n) = 2(n log n − 1.443n)
k=1

• So, W(n) ≤ 2n log n + Θ(n), that is W(n) ∈ Θ(n log n)

Coe cient doubles that of mergeSort approximately
ffi
HeapSort: the Right Choice
• For heapSort, W(n) ∈ Θ(n log n)
• Of course, A(n) ∈ Θ(n log n)
• More good news: HeapSort is an in-space
algorithm (using iteration instead of recursion)

• It will be more competitive if only the

coef cient of the leading term can be
decreased to 1
fi
Number of Comparisons in
xHeap
Procedure:
xHeap(H, K) 2 comparisons are done in
ltering down for one level.
if(H is a leaf) insert K in root (H);
else
Set largerSubHeap;
if(K.key ≥ root(largerSubHeap).key) insert K in root(H)
else
insert root(largerSubHeap) in root(H);
xHeap(largerSubHeap, K);
return
fi
fi
fi
fi
A One-Comparison-per-
Level Fixing
Bubble-Up Heap Algorithm:
void bubbleUpHeap(Element [ ]E, int root, Element K, int vacant)
if(vacant == root) E[vacant] = K;
else Bubbling up from vacant
through to the root, recursively
int parent = vacant/2;
if(K.key ≤ E[parent].key) E[vacant] = K;
else
E[vacant] = E[parent];
bubbleUpHeap(E, root, K, parent);
return
Risky FixHeap In fact, the “risk” is no
more than “no
improvement”

“Vacant” ltering
90 65 90
down: left vs. right
80 65
80 75

70 75
70 35

60 35
25 60

25 50 Element(55) to be
45 50 inserted bubbling up:
45
40 element vs. parent
40 15

15
fi
Improvement by Divide-
and-Conquer
“Vacant” ltering down
90 65 90
only half-way
80 65
80 75

70 75
70 35

35
25 60

25 60 If the element is
45 50 smaller, ltering down
45
50 half-half-way
40 15

The bubbling up will not 40 15

beyond last vacStop

fi
fi
Depth Bounded Filtering
Down
int promote(Element [ ]E, int hStop, int vacant, int h)
int vacStop;
Depth bound
if(h ≤ hStop) vacStop = vacant;
else if(E[2*vacant].key ≤ E[2*vacant+1].key)
E[vacant] = E[2*vacant + 1];
vacStop = promote(E, hStop, 2*vacant + 1, h - 1);
else
E[vacant] = E[2*vacant];
vacStop = promote(E, hStop, 2*vacant, h - 1);
return vacStop;
FixHeap Using Divide-and-
Conquer
void xHeapFast(Element [ ]E, Element K, int vacant, int h)
// h = ⌈log(n + 1)/2⌉ in uppermost call
if(h ≤ 1) Process heap of height 0 or 1;
else
int hStop = h/2;
Int vacStop = promote(E, hStop, vacant, h);
int vacParent = vacStop/2;
if(E[vacParent].key ≤ K.key)
E[vacStop] = E[vacParent];
bubbleUpHeap(E, vacant, K, vacParent);
else
xHeapFast(E, K, vacStop, hStop);
fi
fi
Number of Comparisons in
Accelerated FixHeap
• Moving the vacant one level up or down need one
comparison exactly in promote or bubbleUpHeap.

• In a cycle, t calls of promote and 1 call of bubbleUpHeap are

executed at most. So, the number of comparisons in
promote and bubbleUpHeap calls are:

∑ ⌈ 2k ⌉ ⌈ 2t ⌉
t
h h
+ = h = log(n + 1)
k=1
• At most, lg(h) checks for reverse direction are executed. So,
the number of comparisons in a cycle is at most h+log(h)

• So, for accelerated heapSort: Wn(n) = n log n + Θ(n log log n)

Recursion Equation
of Accelerated heapSort
• The recurrence equation about h, which is
about log(n+1)
T(1) = 2

⌈2 ⌉ (⌈ 2 ⌉ (⌊ 2 ⌋))
h h h
T(h) = + max ,1 + T

• Assuming T(h)≥h, then:

T(1) = 2

⌈2 ⌉ (⌊ 2 ⌋)
h h
T(h) = +1+T
Solving the Recurrence
Equation by Recursive Tree
For sorting a sequence of
size n, n cycles of xHeap
T(n) ⌈h/2⌉ + 1
are executed, so:
n(h + ⌈log(h + 1)⌉)
T(⌊n/2⌋) ⌈h/4⌉ + 1

⌈log(h + 1)⌉ T(⌊n/4⌋) ⌈h/8⌉ + 1

levels

T(1) 1+1
fi
T(1) = 2
Inductive Proof T(h) =
⌈2 ⌉ (⌊ 2 ⌋)
h h
+1+T
• The recurrence equation for xHeapFast:
• Proving the following solution by induction:
T(h) = h + ⌈log(h + 1)⌉
• According to the recurrence equation:
T(h + 1) = ⌈(h + 1)/2⌉ + 1 + T(⌊(h + 1)/2⌋)
• Applying the inductive assumption to the last term:
T(h + 1) = ⌈(h + 1)/2⌉ + 1 + ⌊(h + 1)/2⌋ + ⌈log(⌊(h + 1)/2⌋ + 1)⌉
(It can be proved that for any positive integer:
⌈log(⌊(h)/2⌋ + 1)⌉ + 1 = ⌈log(h + 1)⌉ )
Wn(n) = n log n + Θ(n log log n) For Accelerated Heap
fi
Generalization of a Heap
• d-ary heap
• Structure / partial order
• How to choose “d”?
4-art heap
• Top-down: x the parent node

• Cost: d comparisons in the worst

case

• Bottom-up: x the child node

• Cos: always 1
fi
fi
Not only for Sorting
• Eg1: how to nd the k th max element?

• The cost should be f(k)

• Eg2: how to nd the rst k elements?

• In sorted order?
• Eg3: how to merge k sorted lists?
• Eg4: how to nd the median dynamically?

• ...
fi
fi
fi
fi
Thank you!
Q&A