Heap Sort

Time complexity: O(n log n)

Space complexity: O(1)

Data type: Arrays

Visualization

Comparisons: 0

Reorders: 0

Delay: 1ms

Items: 50

Definition

Heap Sort is a comparison-based sorting algorithm that uses a binary heap data structure to sort elements. It works by first transforming the array into a max-heap (where the parent node is always greater than its children), then repeatedly extracting the maximum element from the heap and rebuilding the heap until all elements are sorted.

Constraints

  • Not a stable sort (does not maintain relative order of equal elements)
  • Poor cache performance compared to Quick Sort and Merge Sort
  • Efficient for large datasets but often slower in practice than Quick Sort
  • Limited adaptability - doesn't take advantage of existing order in input

Step-by-step explanation

Arguments:

  • Array to be sorted - array
  • Heap size - heapSize
  • Current index in heap - i
  • Left child index - left
  • Right child index - right
  • Largest element index - largest

Explanation:

  • Build a max-heap from the input array:
    • Start from the last non-leaf node (parent of last element)
    • Heapify each node to maintain max-heap property
  • Repeatedly extract maximum element from heap:
    • Swap root (maximum element) with last element
    • Reduce heap size by one (excluding sorted elements)
    • Heapify the new root to maintain max-heap property
  • Repeat extraction until heap contains only one element
  • The array is now sorted in ascending order

Returns:

Returns nothing (sorts array in-place)
Modifies the original array instead of returning a new one
No explicit return value (void function in most implementations)

Example

1
#include <vector>
2
#include <algorithm> // for std::swap
3
4
void heapify(std::vector<int>& arr, int n, int i) {
5
int current = i;
6
7
while (true) {
8
int largest = current;
9
int left = 2 * current + 1;
10
int right = 2 * current + 2;
11
12
if (left < n && arr[left] > arr[largest])
13
largest = left;
14
if (right < n && arr[right] > arr[largest])
15
largest = right;
16
17
if (largest == current)
18
break;
19
20
std::swap(arr[current], arr[largest]);
21
current = largest;
22
}
23
}
24
25
void heapSort(std::vector<int>& arr) {
26
int n = (int)arr.size();
27
28
// Build heap (rearrange array)
29
for (int i = n / 2 - 1; i >= 0; i--)
30
heapify(arr, n, i);
31
32
// Extract elements one by one from heap
33
for (int i = n - 1; i > 0; i--) {
34
// Move current root to end
35
std::swap(arr[0], arr[i]);
36
37
// Call max heapify on the reduced heap
38
heapify(arr, i, 0);
39
}
40
}