Heap Sort
Heap Sort Settings
Parent nodes are greater than children (creates ascending order)
Heap Sort Settings
Parent nodes are greater than children (creates ascending order)
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Legend
- • Numbers show element values
- • Bottom labels show array indices
- • Colors indicate current operation
- • Height represents value magnitude
Inspector
Reference implementation of Heap Sort. Select a language tab to view and copy the code.
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 tmp = arr[i]; arr[i] = arr[largest]; arr[largest] = tmp;
heapify(arr, n, largest);
}
}
void heap_sort(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 tmp = arr[0]; arr[0] = arr[i]; arr[i] = tmp;
heapify(arr, n, 0);
}
}#include <vector>
#include <algorithm>
void heapify(std::vector<int>& 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) {
std::swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
void heapSort(std::vector<int>& arr) {
int n = static_cast<int>(arr.size());
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
std::swap(arr[0], arr[i]);
heapify(arr, n, 0);
}
}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, n, 0);
}
}
private static void heapify(int[] 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) {
int temp = arr[i]; arr[i] = arr[largest]; arr[largest] = temp;
heapify(arr, n, largest);
}
}def heap_sort(arr: list[int]) -> None:
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, n, i)
def _heapify(arr: list[int], n: int, i: int) -> None:
largest = i
left, right = 2 * i + 1, 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)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[0], arr[i]] = [arr[i], arr[0]];
heapify(arr, n, 0);
}
}
function heapify(arr, n, i) {
let largest = i;
const 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);
}
}Python — Code Walkthrough
Phase 1 — build heap with range step -1
for i in range(n // 2 - 1, -1, -1): _heapify(arr, n, i)range(start, stop, step) with step = -1 counts downward. Starting at n//2 − 1 (last non-leaf) and ending at 0 builds the heap bottom-up. The stop value -1 means we include index 0.
Phase 2 — extract and reduce heap size
for i in range(n - 1, 0, -1): arr[0], arr[i] = arr[i], arr[0]; _heapify(arr, n, i)i decrements from n-1 to 1. Each iteration swaps the max (root) to position i and then heapifies the reduced heap of size i. Note n is i here, shrinking the heap boundary.
Leading underscore convention
def _heapify(arr, n, i)The _ prefix is a Python convention for "internal/private". It signals that _heapify is a helper for heap_sort and is not intended to be part of the public interface.
Child index arithmetic
left, right = 2 * i + 1, 2 * i + 2Same 0-indexed array-based heap formula as all other languages. Multiple assignment sets both child indices in one line.
Tuple swap on mismatch
arr[i], arr[largest] = arr[largest], arr[i]; _heapify(arr, n, largest)Python's simultaneous assignment swaps without a temp variable. The recursive call then sifts the displaced element down to restore the heap property.