Heap Sort Program with Explanation and Code

2025-11-19 heap sort binary heap max heap sorting algorithms data structures efficient sorting python heap sort c heap sort javascript heap sort php heap sort csharp heap sort algorithm explanation

Heap Sort is an efficient O(n log n) sorting algorithm based on the binary heap structure. This page explains the algorithm step-by-step and includes full programs in Python, C, JavaScript, PHP, and C#. Ideal for students and interview preparation.

Program Explanation

What is Heap Sort?

Heap Sort is an efficient comparison-based sorting algorithm that uses a Binary Heap data structure. It works by converting the array into a max heap, then repeatedly swapping the root (maximum value) with the last element of the heap and reducing the heap size until the array is fully sorted.

Steps to Solve

  1. Build a max heap from the input array.
  2. The largest element will be at the root of the heap.
  3. Swap the root with the last element of the heap.
  4. Reduce the heap size and heapify the root again.
  5. Repeat the process until the heap size becomes 1.
  6. The array is now sorted in ascending order.

Key Points

  • Time Complexity (Best, Average, Worst): O(n log n).
  • Not a stable sort.
  • Heap Sort is an in-place sorting algorithm.
  • Uses binary heap for efficient max/min extraction.
  • Suitable for large datasets.
  • Building the heap takes O(n).

Program Code


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[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)

arr = list(map(int, input("Enter numbers: ").split()))
heap_sort(arr)
print("Sorted array:", arr)
      

#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 n;
    printf("Enter number of elements: ");
    scanf("%d", &n);

    int arr[n];
    printf("Enter elements: ");
    for (int i = 0; i < n; i++)
        scanf("%d", &arr[i]);

    heapSort(arr, n);

    printf("Sorted array: ");
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);

    return 0;
}
      

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 = prompt("Enter numbers:").split(" ").map(Number);
heapSort(arr);
console.log("Sorted array:", arr);
      

using System;

class Program {

    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) {
            (arr[i], arr[largest]) = (arr[largest], arr[i]);
            Heapify(arr, n, largest);
        }
    }

    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--) {
            (arr[0], arr[i]) = (arr[i], arr[0]);
            Heapify(arr, i, 0);
        }
    }

    static void Main() {
        Console.Write("Enter numbers: ");
        int[] arr = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);

        HeapSort(arr);

        Console.Write("Sorted array: ");
        foreach (int x in arr)
            Console.Write(x + " ");
    }
}
      

<?php

function heapify(&$arr, $n, $i) {
    $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);
    }
}

function heapSort(&$arr) {
    $n = count($arr);

    for ($i = intdiv($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);
    }
}

$arr = array_map('intval', explode(" ", readline("Enter numbers: ")));
heapSort($arr);

echo "Sorted array: " . implode(" ", $arr);

?>
1