Algorithms and Problem Solving
Course Number: ITCC103
Lecture 6: Heapsort and Quicksort
Dr. Ouarda Bettaz Nehabova
College of Information Technology
Lusail University
Acknowledgement
These slides are formatted using mainly the following resource:
Introduction to Algorithms 4th Edition, Thomas H. CORMEN, Charles
E. LEISERSON, Ronald L. RIVEST, Clifford STEIN.
I apologies for any non intentionally omitted reference.
College of Information Technology
Lusail University 2
Learning outcomes
At the end of this lecture you should Have:
Understood what is a Heap data structure.
Learned how to build a heap and how to maintain Max-heap property.
Understood how the Heapsort algorithm operates.
Learned about Quicksort algorithm and how it follows the divide and conquer
method.
College of Information Technology
Lusail University 3
Binary tree Data Structure
Edge Root node
A binary tree is a non-linear data structure
with a maximum of two children for each Subtree
parent. Parent
Siblings
Leaf node
Child
College of Information Technology
Lusail University 4
Heap Data Structure
A heap data structure is an array object that
we can view as a nearly complete binary
tree.
Each node of the tree corresponds to an
element of the array.
The tree is completely filled on all levels
except possibly the lowest, which is
filled from the left up to a point.
College of Information Technology
Lusail University 5
Heap Data Structure
An array A[1:n] that represents a heap is an
object with an attribute A.heap-size.
Represents how many elements in the
heap are stored within array A.
Although A[1:n] may contain
numbers, only the elements in A[1:
A.heap-size], where
0 <= A.heap-size<= n, are valid
elements of the Heap.
If A.heap-size =0, then the heap is
empty.
College of Information Technology
Lusail University 6
Heap Data Structure
Height of node = # of edges on a longest
simple path from the node down to a leaf.
Height of heap = height of root = Θ(lg ).
Example: Of a max-heap in array with
h − = 10.
College of Information Technology
Lusail University 7
𝑒
𝑎
𝑝
𝑛
𝑠
𝑖
𝑧
𝑒
Max-heap & Min-heap property
College of Information Technology
Lusail University 8
Heap Data Structure Cont.
The root of the tree is A[1] and
given the index i of a node, there’s a
simple way to compute the indices
of its parent, left child, and right
child with the one-line procedures
PARENT, LEFT, and RIGHT.
College of Information Technology
Lusail University 9
Example
Max-heap with heap-size =10 viewed as:
(a) a binary tree and
(b) an array.
The number within the circle at each node in the tree
is the value stored at that node.
The number above a node is the corresponding index
in the array.
Above and below the array are lines showing parent-
child relationships, with parents always to the left of
their children.
The tree has height 3
The node at index 4 (with value 8) has height 1.
College of Information Technology
Lusail University 10
Maintaining the heap property
MAX-HEAPIFY is important for manipulating max-heaps.
It is used to maintain the max-heap property.
Before MAX-HEAPIFY, [ ] may be smaller than its children.
Assume that left and right subtrees of are max-heaps.
(No violations of max-heap property within the left and right subtrees.
The only violation within the subtree rooted at could be between
and its children.)
After MAX-HEAPIFY, subtree rooted at is a max-heap.
College of Information Technology
Lusail University 11
𝐴
𝑖𝑖𝑖𝑖
𝑖
Pseudocode
College of Information Technology
Lusail University 12
The way Max-Heapify works
Compare [ ], [ ( )], and [ ( )].
If necessary, swap [ ] with the larger of the two children to preserve
heap property.
Continue this process of comparing and swapping down the heap, until
subtree rooted at is max-heap.
If we hit a leaf, then the subtree rooted at the leaf is trivially a max-heap.
College of Information Technology
Lusail University 13
𝐴
𝐴
𝐴
𝐴
𝑖
𝑖
𝐿
𝑅
𝑖
𝐸
𝐼
𝐺
𝐹
𝐻
𝑇
𝑇
𝑖
𝑖
Example
• Run MAX-HEAPIFY on the following heap example.
College of Information Technology
Lusail University 14
Building a Heap
The following procedure, given an unordered array [1: ], will
produce a max-heap of the elements in .
College of Information Technology
Lusail University
15
𝐴
𝑛𝐴
𝑛
Example
Building a max-heap by calling BUILD-MAX-HEAP( , 10) on the
following unsorted array [1: 10] results in the first heap example.
College of Information Technology
Lusail University
16
𝐴
𝐴
Example Cont.
College of Information Technology
17
Lusail University
The Heapsort Algorithm
Given an input array, the heapsort algorithm acts as follows:
Builds a max-heap from the array.
Starting with the root (the maximum element), the algorithm places
the maximum element into the correct place in the array by
swapping it with the element in the last position in the array.
“Discard” this last node (knowing that it is in its correct place) by
decreasing the heap size, and calling MAX-HEAPIFY on the new
(possibly incorrectly-placed) root.
Repeat this “discarding” process until only one node (the smallest
element) remains, and therefore is in the correct place in the array.
College of Information Technology
Lusail University
18
Pseudocode
College of Information Technology
Lusail University
19
Example
Nodes with heavy outline are no longer in the heap.
College of Information Technology 20
20
Lusail University
Heapsort running time
Worse case tuning time is O(nlgn) like merge sort.
Sort in place like insertion sort
Combines the best of both algorithms.
Though heap sort is great algorithm, a well implemented quick
sort usually beats it in practice.
College of Information Technology
Lusail University
21
Quicksort
College of Information Technology
Lusail University
22
Pseudocode
Initial call is QUICKSORT( , 1, ).
College of Information Technology
Lusail University
23
𝐴
𝑛
Partitioning
Partition subarray [ : ] by the following procedure:
Initial call is QUICKSORT( , 1, ).
PARTITION always selects the last element [ ] in the subarray [ : ]
as the pivot—the element around which to partition.
College of Information Technology 24
Lusail University
𝐴
𝐴
𝐴
𝑟
𝑝
𝑝
𝑟
𝑟
𝐴
𝑛
Partitioning Cont.
College of Information Technology 25
Lusail University
Example
College of Information Technology 26
Lusail University
Performance of quicksort
The running time of quicksort depends on the partitioning of the
subarrays:
If the subarrays are balanced, then quicksort can run as fast as
mergesort.
If they are unbalanced, then quicksort can run as slowly as insertion
sort.
Worst-case running time is Θ(n2).
College of Information Technology 27
Lusail University
End of the Lecture
College of Information Technology 28
Lusail University
Sources
Thomas H. CORMEN, et al.
Introduction to Algorithms.
The MIT Press, Cambridge, Massachusetts London, England,
ISBN 9780262046305,
2022.
College of Information Technology 29
Lusail University
