Heap Sort
In this page:
Basic Idea
Heap sort first rearranges the array into a max heap, where every parent value is at least as large as its children, then repeatedly removes the largest value from the top and places it at the end of the array until nothing remains.
Example: Basic Idea
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
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[] = {4, 10, 3, 5, 1};
heapSort(arr, 5);
for (int x : arr) cout << x << " ";
return 0;
}public class Main {
static void heapify(int[] arr, int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t; heapify(arr, n, largest); }
}
static 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 t = arr[0]; arr[0] = arr[i]; arr[i] = t; heapify(arr, i, 0); }
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapSort(arr, 5);
System.out.println(java.util.Arrays.toString(arr));
}
}def heapify(arr, n, i):
largest = i
l, r = 2 * i + 1, 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
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)
arr = [4, 10, 3, 5, 1]
heap_sort(arr)
print(arr)#include <stdio.h>
void swapv(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { swapv(&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--) { swapv(&arr[0], &arr[i]); heapify(arr, i, 0); }
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
heapSort(arr, 5);
for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Step by Step
Building the heap and removing its maximum are both done using the same 'sift down' operation: after removing the root, the last element takes its place and is swapped downward with its larger child until the heap property is restored.
Example: Step by Step
#include <iostream>
using namespace std;
int main() {
cout << "Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap");
}
}print("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap")#include <stdio.h>
int main() {
printf("Build max heap first, then repeatedly swap root (max) to the end and sift down the reduced heap");
return 0;
}Login to try C/C++/Java code in the editor
Small Array
Tracing heap sort on a small array like [4, 10, 3, 5, 1] shows the initial heap-building phase followed by repeated root-removal steps, each one shrinking the heap by one and growing the sorted portion at the array's end.
Example: Small Array
#include <iostream>
using namespace std;
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { swap(arr[i], arr[largest]); heapify(arr, n, largest); }
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
for (int i = 1 / 2 - 1; i >= 0; i--) heapify(arr, 5, i);
heapify(arr, 5, 0);
for (int x : arr) cout << x << " ";
return 0;
}public class Main {
static void heapify(int[] arr, int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { int t = arr[i]; arr[i] = arr[largest]; arr[largest] = t; heapify(arr, n, largest); }
}
public static void main(String[] args) {
int[] arr = {4, 10, 3, 5, 1};
heapify(arr, 5, 0);
System.out.println(java.util.Arrays.toString(arr));
}
}def heapify(arr, n, i):
largest = i
l, r = 2 * i + 1, 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
arr = [4, 10, 3, 5, 1]
heapify(arr, 5, 0)
print(arr)#include <stdio.h>
void swapv(int *a, int *b) { int t = *a; *a = *b; *b = t; }
void heapify(int arr[], int n, int i) {
int largest = i, l = 2 * i + 1, r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) largest = l;
if (r < n && arr[r] > arr[largest]) largest = r;
if (largest != i) { swapv(&arr[i], &arr[largest]); heapify(arr, n, largest); }
}
int main() {
int arr[] = {4, 10, 3, 5, 1};
heapify(arr, 5, 0);
for (int i = 0; i < 5; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Practice
Unlike merge sort, heap sort needs no extra array — the heap and the growing sorted region both live inside the original array, which is why heap sort is valued when memory is constrained despite being generally a bit slower in practice than a well-tuned quicksort.
Example: Practice
#include <iostream>
using namespace std;
int main() {
cout << "Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array");
}
}print("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array")#include <stdio.h>
int main() {
printf("Unlike merge sort, heap sort needs no extra array; the heap and sorted region share the original array");
return 0;
}Login to try C/C++/Java code in the editor
Summary
Heap sort guarantees O(n log n) time in every case, with only O(1) extra space, making it a reliable middle ground between merge sort's guaranteed time (but extra memory) and quicksort's average speed (but worst-case risk).
Example: Summary
#include <iostream>
using namespace std;
int main() {
cout << "Heap sort: guaranteed O(n log n) time with only O(1) extra space";
return 0;
}public class Main {
public static void main(String[] args) {
System.out.println("Heap sort: guaranteed O(n log n) time with only O(1) extra space");
}
}print("Heap sort: guaranteed O(n log n) time with only O(1) extra space")#include <stdio.h>
int main() {
printf("Heap sort: guaranteed O(n log n) time with only O(1) extra space");
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 9 topics to unlock
0/9 topics done
Complete these topics first: