A heap is a special tree-based data structure that is usually implemented as an array. It is a complete binary tree, which means all levels are completely filled except possibly the last level, and the last level is filled from left to right.
There are two common types:
For a node at index i in a 0-indexed array:
2i + 12i + 2(i - 1) / 2Heaps are useful when we repeatedly need the largest or smallest element. Because the root always stores the extreme value, insertion and deletion can be done efficiently in O(log n).
Heaps are widely used in:
Heap Sort is a comparison-based sorting algorithm that uses a max-heap to sort elements in ascending order.
It has two main phases:
The result is a sorted array in-place.
If the array is arranged as a max-heap, then the largest element is always at the root. So:
Repeating this places the elements from largest to smallest at the end of the array, which gives ascending order overall.
| Case | Time | Space | Stable? |
|---|---|---|---|
| Best | O(n log n) | O(1) | No |
| Average | O(n log n) | O(1) | No |
| Worst | O(n log n) | O(1) | No |
Heap Sort is valued because its worst-case time is guaranteed to stay O(n log n), unlike Quick Sort which can degrade to O(n^2) in the worst case.
At first glance, it may seem that building a heap should take O(n log n) because heapify can take O(log n). But the bottom levels of the tree contain many nodes that require very little work, while only a few top-level nodes can move far downward.
Because of this distribution, the total cost of building the heap from bottom to top is actually O(n).
This is an important exam point: heap construction by bottom-up heapify is O(n), not O(n log n).
Heapify restores the heap property for a subtree whose root may violate the heap condition.
For a max-heap:
Heapify takes O(log n) in the worst case because the element may move down through the height of the heap.
import java.util.Arrays;
public class HeapSort {
static void heapify(int[] arr, int heapSize, int i) {
int largest = i;
int left = 2 * i + 1;
int right = 2 * i + 2;
if (left < heapSize && arr[left] > arr[largest]) {
largest = left;
}
if (right < heapSize && arr[right] > arr[largest]) {
largest = right;
}
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, heapSize, largest);
}
}
static void heapSort(int[] arr) {
int n = arr.length;
// Build max-heap.
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
// Move current maximum to the end one by one.
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
static class MaxHeap {
int[] heap;
int size;
MaxHeap(int capacity) {
heap = new int[capacity];
size = 0;
}
void insert(int value) {
heap[size] = value;
int i = size++;
while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
int temp = heap[i];
heap[i] = heap[(i - 1) / 2];
heap[(i - 1) / 2] = temp;
i = (i - 1) / 2;
}
}
int extractMax() {
int max = heap[0];
heap[0] = heap[--size];
heapify(heap, size, 0);
return max;
}
}
public static void main(String[] args) {
int[] arr = {12, 11, 13, 5, 6, 7};
System.out.println("Before: " + Arrays.toString(arr));
heapSort(arr);
System.out.println("After: " + Arrays.toString(arr));
MaxHeap pq = new MaxHeap(10);
pq.insert(3);
pq.insert(1);
pq.insert(4);
pq.insert(1);
pq.insert(5);
System.out.print("Max extractions: ");
while (pq.size > 0) {
System.out.print(pq.extractMax() + " ");
}
}
}Consider the array [12, 11, 13, 5, 6, 7].
[13, 11, 12, 5, 6, 7].A few steps look like this:
[13, 11, 12, 5, 6, 7][7, 11, 12, 5, 6, 13][12, 11, 7, 5, 6, 13][6, 11, 7, 5, 12, 13][11, 6, 7, 5, 12, 13][5, 6, 7, 11, 12, 13]A sorting algorithm is stable if equal elements keep their original relative order. Heap Sort is not stable because swapping the root with the last element can change the relative order of equal values.
Heap Sort is a good choice when:
It is less attractive when cache performance matters heavily, because heap operations jump around in memory more than algorithms like Quick Sort.
| Algorithm | Best | Average | Worst | Space | Stable | Main Strength |
|---|---|---|---|---|---|---|
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Usually fastest in practice |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stable and predictable |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Worst-case guarantee with in-place sorting |
| Algorithm | Best | Average | Worst | Space | Stable | Notes |
|---|---|---|---|---|---|---|
| Bubble Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Simple but slow |
| Selection Sort | O(n^2) | O(n^2) | O(n^2) | O(1) | No | Few swaps |
| Insertion Sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes | Good for small or nearly sorted data |
| Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | Yes | Stable and guaranteed |
| Quick Sort | O(n log n) | O(n log n) | O(n^2) | O(log n) | No | Usually fastest in practice |
| Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | No | Guaranteed and in-place |
| Counting Sort | O(n + k) | O(n + k) | O(n + k) | O(k) | Yes | For integer keys in a limited range |
| Radix Sort | O(nk) | O(nk) | O(nk) | O(n + k) | Yes | Non-comparison sorting |
Explore 500+ free tutorials across 20+ languages and frameworks.