Heap Sort

Understanding the Problem

We are given an array of numbers and we need to sort them in increasing order. Instead of using built-in sorting, we will implement Heap Sort, which is an efficient comparison-based sorting technique based on a binary heap data structure. Our goal is to understand how heap sort works step-by-step, including edge cases, using a beginner-friendly example.

Example to Understand

Let’s consider the input array: [4, 10, 3, 5, 1]. We want to sort this into: [1, 3, 4, 5, 10].

Step-by-Step Explanation

• Step 1: Build a Max Heap
  A Max Heap is a binary tree where each parent node is greater than or equal to its children. For the array [4, 10, 3, 5, 1], we reorganize the array to follow the max heap property: [10, 5, 3, 4, 1].
• Step 2: Swap the Max Element with the Last
  Swap the first element (maximum) with the last element: [1, 5, 3, 4, 10]. Now 10 is in its correct sorted position.
• Step 3: Heapify the Root
  After removing the largest element (by reducing heap size), we heapify the new root (1) to maintain max heap: [5, 4, 3, 1, 10].
• Step 4: Repeat the Process
  Continue the swap and heapify until the heap is reduced to one element:
  • Swap 5 and 1 → [1, 4, 3, 5, 10], heapify → [4, 1, 3, 5, 10]
  • Swap 4 and 3 → [3, 1, 4, 5, 10], heapify → [3, 1, 4, 5, 10]
  • Swap 3 and 1 → [1, 3, 4, 5, 10], done.
• Final Sorted Array: [1, 3, 4, 5, 10]

Handling Edge Cases

Case 1 - Single Element

Input: [1]

• Only one element is already sorted.
• No heap to build, return as-is: [1]

Case 2 - Empty Array

Input: []

• Nothing to sort. Return empty array immediately.

Case 3 - Reverse Sorted Input

Input: [9, 8, 7, 6, 5]

• It’s already in max order, which helps form the max heap directly: [9, 8, 7, 6, 5].
• Swap and heapify process will still work as normal.
• Final sorted output: [5, 6, 7, 8, 9]

Case 4 - All Elements Are Same

Input: [5, 5, 5, 5]

• Heap sort works fine. Swapping and heapifying won't change positions, but the algorithm still runs.
• Sorted output is the same: [5, 5, 5, 5]

1. Build a max heap from the input array.
2. The largest element is now at the root of the heap.
3. Swap the root with the last element, then reduce the heap size by one.
4. Heapify the root to maintain the heap property.
5. Repeat steps 3 and 4 until the heap size is 1.

#include <stdio.h>

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        int temp = arr[i];
        arr[i] = arr[largest];
        arr[largest] = temp;
        heapify(arr, n, largest);
    }
}

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[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array is: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    return 0;
}

#include <iostream>
using namespace std;

void heapify(int arr[], int n, int i) {
    int largest = i;
    int left = 2 * i + 1;
    int right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest])
        largest = left;
    if (right < n && arr[right] > arr[largest])
        largest = right;
    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);
    }
}

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[] = {6, 3, 8, 2, 7, 4};
    int n = sizeof(arr)/sizeof(arr[0]);
    heapSort(arr, n);
    cout << "Sorted array is: ";
    for (int i = 0; i < n; i++)
        cout << arr[i] << " ";
    return 0;
}

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
    if left < n and arr[left] > arr[largest]:
        largest = left
    if right < n and arr[right] > arr[largest]:
        largest = right
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

def heap_sort(arr):
    n = len(arr)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

arr = [6, 3, 8, 2, 7, 4]
heap_sort(arr)
print("Sorted array is:", arr)

public class HeapSort {
    public static void heapify(int arr[], int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        if (left < n && arr[left] > arr[largest]) largest = left;
        if (right < n && arr[right] > arr[largest]) largest = right;
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
            heapify(arr, n, largest);
        }
    }
    public static void heapSort(int arr[]) {
        int n = arr.length;
        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);
        }
    }
    public static void main(String[] args) {
        int[] arr = {6, 3, 8, 2, 7, 4};
        heapSort(arr);
        System.out.print("Sorted array is: ");
        for (int val : arr)
            System.out.print(val + " ");
    }
}

function heapify(arr, n, i) {
    let largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}
function heapSort(arr) {
    let n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
}
let arr = [6, 3, 8, 2, 7, 4];
heapSort(arr);
console.log("Sorted array is:", arr);

package main
import "fmt"

func heapify(arr []int, n int, i int) {
    largest := i
    left := 2*i + 1
    right := 2*i + 2
    if left < n && arr[left] > arr[largest] {
        largest = left
    }
    if right < n && arr[right] > arr[largest] {
        largest = right
    }
    if largest != i {
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
    }
}

func heapSort(arr []int) {
    n := len(arr)
    for i := n/2 - 1; i >= 0; i-- {
        heapify(arr, n, i)
    }
    for i := n - 1; i > 0; i-- {
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    }
}

func main() {
    arr := []int{6, 3, 8, 2, 7, 4}
    heapSort(arr)
    fmt.Println("Sorted array is:", arr)
}

fn heapify(arr: &mut Vec<i32>, n: usize, i: usize) {
    let mut largest = i;
    let left = 2 * i + 1;
    let right = 2 * i + 2;

    if left < n && arr[left] > arr[largest] {
        largest = left;
    }
    if right < n && arr[right] > arr[largest] {
        largest = right;
    }
    if largest != i {
        arr.swap(i, largest);
        heapify(arr, n, largest);
    }
}

fn heap_sort(arr: &mut Vec<i32>) {
    let n = arr.len();
    for i in (0..n/2).rev() {
        heapify(arr, n, i);
    }
    for i in (1..n).rev() {
        arr.swap(0, i);
        heapify(arr, i, 0);
    }
}

fn main() {
    let mut arr = vec![6, 3, 8, 2, 7, 4];
    heap_sort(&mut arr);
    println!("Sorted array is: {:?}", arr);
}

fun heapify(arr: IntArray, n: Int, i: Int) {
    var largest = i
    val left = 2 * i + 1
    val right = 2 * i + 2
    if (left < n && arr[left] > arr[largest]) largest = left
    if (right < n && arr[right] > arr[largest]) largest = right
    if (largest != i) {
        val temp = arr[i]
        arr[i] = arr[largest]
        arr[largest] = temp
        heapify(arr, n, largest)
    }
}

fun heapSort(arr: IntArray) {
    val n = arr.size
    for (i in n / 2 - 1 downTo 0) {
        heapify(arr, n, i)
    }
    for (i in n - 1 downTo 1) {
        val temp = arr[0]
        arr[0] = arr[i]
        arr[i] = temp
        heapify(arr, i, 0)
    }
}

fun main() {
    val arr = intArrayOf(6, 3, 8, 2, 7, 4)
    heapSort(arr)
    println("Sorted array is: ${arr.joinToString(" ")}")
}

function heapify(arr: number[], n: number, i: number): void {
    let largest = i;
    const left = 2 * i + 1;
    const right = 2 * i + 2;
    if (left < n && arr[left] > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;
    if (largest !== i) {
        [arr[i], arr[largest]] = [arr[largest], arr[i]];
        heapify(arr, n, largest);
    }
}

function heapSort(arr: number[]): void {
    const n = arr.length;
    for (let i = Math.floor(n / 2) - 1; i >= 0; i--)
        heapify(arr, n, i);
    for (let i = n - 1; i > 0; i--) {
        [arr[0], arr[i]] = [arr[i], arr[0]];
        heapify(arr, i, 0);
    }
}

const arr: number[] = [6, 3, 8, 2, 7, 4];
heapSort(arr);
console.log("Sorted array is:", arr);

Time complexity

Space complexity

O(1)

Heap sort is performed in-place with no need for additional memory allocation beyond a few variables, resulting in constant auxiliary space usage.