Heap Sort
Sayan Sikder
SCOPE, VIT University, Vellore
2023
Heap
The binary heap data structures is an array that can be viewed as a complete
binary tree. Each node of the binary tree corresponds to an element of the
array. It stores a collection of objects (with keys) maintaining heap order.
19
12 16
1 4 7
19 12 16 1 4 7
Array A
As an array
In order to represent a tree using an array, the numbering of
nodes can start either from 0–(n-1) or 1– n, consider as
follows:
Case 1: (0—n-1)
if (say)father=p;
then left_son=(2*p)+1;
and right_son=(2*p)+2;
Case 2: 1—n
if (say)father=p;
then left_son=(2*p);
and right_son=(2*p)+1;
Heap order
• For every node v, other than the root, the key stored
in v is greater or equal (smaller or equal for max
heap) than the key stored in the parent of v.
• In this case the maximum value is stored in the root
Max Heap & Min Heap
Max Heap
✓ Store data in ascending order
✓ Has property of
✓ A[Parent(i)] ≥ A[i]
Min Heap
✓ Store data in descending order
✓ Has property of
✓ A[Parent(i)] ≤ A[i]
Max Heap example
19
12 16
1 4 7
19 12 16 1 4 7
Array A
Min Heap example
4 16
7 12 19
1 4 16 7 12 19
Array A
Insertion
Algorithm
• Add the new element to the next available position at the lowest level
• Restore the max-heap property if violated
• General strategy is percolate up (or bubble up): if the parent of the
element is smaller than the element, then interchange the parent and child.
OR
• Restore the min-heap property if violated
• General strategy is percolate up (or bubble up): if the parent of the
element is larger than the element, then interchange the parent and child.
Example
Deletion
Delete max
• Copy the last number to the root (overwrite the maximum element
stored there).
• Restore the max heap property by percolate down.
Delete min
• Copy the last number to the root (overwrite the minimum element
stored there).
• Restore the min heap property by percolate down.
Procedures
• Heapify
• Build Heap
• Heap Sort
To sort the elements in the decreasing order, use a min heap
To sort the elements in the increasing order, use a max heap
Heapify
Heapify picks the largest child key and compare it to the parent
key. If parent key is larger than heapify quits, otherwise it swaps
the parent key with the largest child key. So that the parent is now
becomes larger than its children.
Heapify(A, i)
{
l left(i)
r right(i)
if l <= heapsize[A] and A[l] > A[i]
then largest l
else largest i
if r <= heapsize[A] and A[r] > A[largest]
then largest r
if largest != i
then swap A[i] → A[largest]
Heapify(A, largest)
}
Example
Build Heap
We can use the procedure 'Heapify' in a bottom-up fashion to
convert an array A[1 . . n] into a heap. Since the elements in the
subarray A[n/2 +1 . . n] are all leaves, the procedure BUILD_HEAP
goes through the remaining nodes of the tree and runs 'Heapify' on
each one. The bottom-up order of processing node guarantees that
the subtree rooted at children are heap before 'Heapify' is run at
their parent.
Buildheap(A)
{
heapsize[A] length[A]
for i |length[A]/2 //down to 1
do Heapify(A, i)
}
Heap Sort
The heap sort algorithm starts by using procedure BUILD-HEAP to
build a heap on the input array A[1 . . n]. Since the maximum
element of the array stored at the root A[1], it can be put into its
correct final position by exchanging it with A[n] (the last element in
A). If we now discard node n from the heap than the remaining
elements can be made into heap. Note that the new element at the
root may violate the heap property. All that is needed to restore the
heap property.
Heapsort(A)
{
Buildheap(A)
for i length[A] //down to 2
do swap A[1] → A[i]
heapsize[A] heapsize[A] - 1
Heapify(A, 1)
}
Analysis
• Build Heap Algorithm will run in O(n) time
• There are n-1 calls to Heapify each call requires O(log n) time
• Heap sort program combine Build Heap program and Heapify,
therefore it has the running time of O(n log n) time
• Total time complexity: O(n log n)
