Heap Sort

Time Complexity

Best	Average	Worst
Ω(n log(n))	Θ(n log(n))	O(n log(n))

Space Complexity

Worst
O(1)

Overview

Before proceeding with this algorithm (HeapSort), make sure you know what the Heap data structure is. If you already know what Heap and Heap Property are, you'll have an easy time understanding this algorithm. If you don't know that, stop now and first learn Heap in the Trees section - here.

That was important to mention, but now let's get to the topic!

Heapsort is a sorting algorithm that leverages the heap data structure to efficiently sort elements in an array. The algorithm's main steps can be summarized as follows:

Build Max Heap from the input array.
Swap and remove the root element (this will be the largest sorted element).
Then heapify and repeat each step utilizing the max heap property (the root element will always be the largest element).

Heapsort's key advantage is that it's a very efficient algorithm in regards to time and space complexity. It has an average and worst-case time complexity of O(n log n), so it's definitely a useful choice for sorting large datasets. Also, it has a space complexity of O(1) because the input array can be organized into a heap "in-place" - it doesn't require the creation of additional data structures.

However, it's worth noting that heapsort is not a stable sorting algorithm, meaning the order of equal elements might not be preserved in the sorted output, which sometimes makes it not the best choice despite how efficient it is.

And to explain the example from the animation in detail:

Build a max heap from the input array.

Start with the original array: [7, 1, 3, 5, 4, 2, 6]

Convert it into a max heap (heapify): [7, 5, 6, 1, 4, 2, 3]

Swap the root element (largest) with the last element in the heap.

Swap 7 (root) with 3 (last element): [3, 5, 6, 1, 4, 2, 7]

Remove the last element (previously the root, now the largest) from the heap.

Now the heap after removing the last element is: [3, 5, 6, 1, 4, 2]

Heapify the remaining elements to maintain the max heap property.

Heapify the remaining elements starting from the root (index 0): [6, 5, 2, 1, 4, 3]

Repeat steps 2-4 until the heap is empty, as follows:

Swap 6 (root) with 3 (last element): [3, 5, 2, 1, 4, 6]

Now the heap after removing the last element is: [3, 5, 2, 1, 4]

Heapify the remaining elements starting from the root (index 0): [5, 4, 2, 1, 3]

Swap 5 (root) with 3 (last element): [3, 4, 2, 1, 5]

Now the heap after removing the last element is: [3, 4, 2, 1]

Heapify the remaining elements starting from the root (index 0): [4, 3, 2, 1]

Swap 4 (root) with 1 (last element): [1, 3, 2, 4]

Now the heap after removing the last element is: [1, 3, 2]

Heapify the remaining elements starting from the root (index 0): [3, 1, 2]

Swap 3 (root) with 2 (last element): [2, 1, 3]

Now the heap after removing the last element is: [2, 1]

Heap after removing the last element: [1]

The array is now sorted in ascending order: [1, 2, 3, 4, 5, 6, 7].

If you were able to understand how HeapSort works so far by the explanation and the animation - that's fantastic! But if you are unsure about anything, don't try to understand it here but as already mentioned - learn Heap itself in the Trees section.

Code

def heapify(arr, n, i):
    largest = i
    left = 2 * i + 1
    right = 2 * i + 2
 
    if left < n and arr[i] < arr[left]:
        largest = left
 
    if right < n and arr[largest] < arr[right]:
        largest = right
 
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)
 
def heapSort(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 = [7, 1, 3, 5, 4, 2, 6]
heapSort(arr)
print("Sorted array:", arr)

function heapify(arr, n, i) {
  let largest = i;
  const left = 2 * i + 1;
  const right = 2 * i + 2;
 
  if (left < n && arr[i] < arr[left]) {
    largest = left;
  }
 
  if (right < n && arr[largest] < arr[right]) {
    largest = right;
  }
 
  if (largest !== i) {
    [arr[i], arr[largest]] = [arr[largest], arr[i]];
    heapify(arr, n, largest);
  }
}
 
function heapSort(arr) {
  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[i], arr[0]] = [arr[0], arr[i]];
    heapify(arr, i, 0);
  }
}
 
const arr = [7, 1, 3, 5, 4, 2, 6];
heapSort(arr);
console.log("Sorted array:", arr);

 
import java.util.Arrays;
 
public class HeapSort {
    private 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[i] < arr[left]) {
            largest = left;
        }
 
        if (right < n && arr[largest] < arr[right]) {
            largest = right;
        }
 
        if (largest != i) {
            int temp = arr[i];
            arr[i] = arr[largest];
            arr[largest] = temp;
 
            heapify(arr, n, largest);
        }
    }
 
    private 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 = {7, 1, 3, 5, 4, 2, 6};
        heapSort(arr);
        System.out.println("Sorted array: " + Arrays.toString(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[i] < arr[left]) {
        largest = left;
    }
 
    if (right < n && arr[largest] < arr[right]) {
        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[] = {7, 1, 3, 5, 4, 2, 6};
    int n = sizeof(arr) / sizeof(arr[0]);
    heapSort(arr, n);
    printf("Sorted array: ");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

function heapify(&$arr, $n, $i) {
    $largest = $i;
    $left = 2 * $i + 1;
    $right = 2 * $i + 2;
 
    if ($left < $n && $arr[$i] < $arr[$left]) {
        $largest = $left;
    }
 
    if ($right < $n && $arr[$largest] < $arr[$right]) {
        $largest = $right;
    }
 
    if ($largest != $i) {
        list($arr[$i], $arr[$largest]) = array($arr[$largest], $arr[$i]); // Swap
        heapify($arr, $n, $largest);
    }
}
 
function heapSort(&$arr) {
    $n = count($arr);
 
    for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
        heapify($arr, $n, $i);
    }
 
    for ($i = $n - 1; $i >= 0; $i--) {
        list($arr[0], $arr[$i]) = array($arr[$i], $arr[0]); // Swap
        heapify($arr, $i, 0);
    }
}
 
// Example usage:
$arr = [7, 1, 3, 5, 4, 2, 6];
heapSort($arr);
echo "Sorted array: " . implode(", ", $arr);

We always try to improve this course so if you spot errors, inconsistencies or other issues, contact us.

Counting Sort Merge Sort