Lecture Notes: Heap Sort
Overview: Heap Sort is a comparison-based sorting technique based on a Binary Heap data
structure. It can be thought of as an optimization over selection sort where we use a heap to find
the maximum or minimum element efficiently rather than performing a linear scan.
1. Concept and Mechanism
● Data Structure: Binary Heap (A complete binary tree where parent nodes follow a strict
heap property relative to children).
● Max-Heap: Parent node value >= child node values. Used for sorting in ascending order.
● Time Complexity: Best, Worst, and Average Case: O(n log n)
● Space Complexity: O(1) (In-place sorting)
2. Detailed Step-by-Step Example
Let's trace the process of Heap Sort on an array [4, 10, 3, 5, 1] by treating it as a flat array
representation of a binary tree.
Phase Array State Representation Logical Action / Heapification
Description
1. Build Max-Heap [4, 10, 3, 5, 1] Start heapifying from the last
non-leaf node (index 1: value
10). 10 is greater than its
child 5 and 1, so no change.
1. Build Max-Heap [10, 5, 3, 4, 1] Move to index 0 (value 4). Its
children are 10 and 3. Swap
4 and 10. Then heapify
downwards: swap 4 and 5.
Max-heap complete.
2. Sort Step 1 [5, 4, 3, 1] | [10] Swap the root (10) with the
last element (1). Isolate 10.
Heapify the remaining tree.
Root 1 swaps with 5, then
with 4.
2. Sort Step 2 [4, 1, 3] | [5, 10] Swap root (5) with last active
element (1). Isolate 5.
Heapify remaining. Root 1
Phase Array State Representation Logical Action / Heapification
Description
swaps with 4.
2. Sort Step 3 [3, 1] | [4, 5, 10] Swap root (4) with last active
element (3). Isolate 4.
Heapify remaining. Root 1
swaps with 3.
2. Sort Step 4 [1] | [3, 4, 5, 10] Swap root (3) with last active
element (1). Isolate 3. Only
one element remains.
Finished [1, 3, 4, 5, 10] The array is now fully sorted
in ascending order.
3. Implementation in C
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int swap = arr[i];
arr[i] = arr[largest];
arr[largest] = swap;
// Recursively heapify the affected sub-tree
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
// Build heap (rearrange array)
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// One by one extract an element from heap
for (int i = n - 1; i > 0; i--) {
// Move current root to end
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// call max heapify on the reduced heap
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
int n = sizeof(arr) / sizeof(arr[0]);
heapSort(arr, n);
printf("Sorted array: \n");
for (int i = 0; i < n; ++i) printf("%d ", arr[i]);
return 0;
}