Heap Sort
Definition
Heap Sort is a comparison-based sorting technique based on the Binary Heap data structure. It is similar to Selection Sort where we first find the maximum element and place the maximum element at the end. We repeat the same process for the remaining elements.
How it Works (Step-by-Step)
- Build a Max Heap: First, organize the messy array into a valid Max Heap structure. This puts the largest item at the very start of the array.
- Swap: Swap the first element (largest) with the last element. The largest item is now sorted at the end of the array.
- Heapify: The remaining elements at the top are now disorganized. “Heapify” (re-organize) them so they form a Max Heap again.
- Repeat: Repeat steps 2 and 3 until the entire array is sorted.
Example
Unsorted Array: [4, 10, 3, 5, 1]
- Build Max Heap: [10, 5, 3, 4, 1]
- Swap Root (10) with Last (1): [1, 5, 3, 4, 10] (10 is now sorted)
- Heapify the rest: New Max Heap is [5, 4, 3, 1]
- Swap Root (5) with Last (1): [1, 4, 3, 5, 10] (5 and 10 are sorted)
- Repeat…
Code Example
PythonJavaCC++
# Heapify subtree rooted at index i
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
# Check left child
if l arr[largest]:
largest = l
# Check right child
if r arr[largest]:
largest = r
# Swap and continue heapifying
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heapSort(arr):
n = len(arr)
# Build max heap
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# Extract elements from heap
for i in range(n - 1, 0, -1):
arr[i], arr[0] = arr[0], arr[i]
heapify(arr, i, 0)
arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
print("Sorted array is:", arr)
public class HeapSort {
// Heapify subtree
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l arr[largest])
largest = l;
if (r arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[]) {
int n = arr.length;
// Build max heap
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
// Extract elements
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
public static void main(String args[]) {
int arr[] = {12,11,13,5,6,7};
HeapSort obj = new HeapSort();
obj.heapSort(arr);
System.out.print("Sorted array: ");
for (int i : arr)
System.out.print(i + " ");
}
}
#include <stdio.h>
// Heapify subtree
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l arr[largest])
largest = l;
if (r arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
// Heap sort
void heapSort(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12,11,13,5,6,7};
int n = 6;
heapSort(arr, n);
printf("Sorted array: ");
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
#include <iostream>
using namespace std;
// Heapify subtree
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l arr[largest])
largest = l;
if (r arr[largest])
largest = r;
if (largest != i) {
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// Heap sort
void heapSort(int arr[], int n) {
for (int i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
int main() {
int arr[] = {12,11,13,5,6,7};
int n = 6;
heapSort(arr, n);
cout << "Sorted array: ";
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Complexity Analysis
- Time Complexity: O(n log n) for best, average, and worst cases. This makes it very consistent.
- Space Complexity: O(1). It sorts “in-place,” meaning it doesn’t need extra memory arrays like Merge Sort does.
Use Cases
- Embedded Systems: Because it uses fixed memory (O(1) space), it’s great for systems with very limited RAM (like sorting on a microcontroller).
- Safety-Critical Systems: Since its worst-case scenario is still O(n log n) (unlike QuickSort which can degrade to O(n^2), it is used where predictable timing is mandatory.