Heaps & Heap Sort · Data Structures

A binary heap is a complete binary tree with the heap property:

Max-heap: every parent ≥ its children, so the largest key is at the root.
Min-heap: every parent ≤ its children, so the smallest key is at the root.

Unlike a BST, a heap says nothing about left versus right — only parent versus child.

A max-heap. Every parent is larger than its children; 90, the maximum, is the root.

Stored in an array

Because a heap is complete, it fits perfectly in an array with no gaps — no pointers needed. For index i (0-based): parent (i − 1) / 2, left child 2i + 1, right child 2i + 2.

The same heap stored level by level.

Insert: add at the end, then sift up

Put the new key in the next free slot (keeping the tree complete), then swap it with its parent while it is larger. At most one swap per level: O(log n).

Extract max: move the last key to the root, then sift down

Remove the root (the maximum). Move the last element to the root, then swap it with its larger child while it is smaller than that child. Also O(log n).

#include <stdio.h>

int heap[100], n = 0;

void swap(int *a, int *b) { int t = *a; *a = *b; *b = t; }

void siftUp(int i) {
    while (i > 0 && heap[(i - 1) / 2] < heap[i]) {
        swap(&heap[(i - 1) / 2], &heap[i]);
        i = (i - 1) / 2;
    }
}

void siftDown(int i) {
    for (;;) {
        int largest = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && heap[l] > heap[largest]) largest = l;
        if (r < n && heap[r] > heap[largest]) largest = r;
        if (largest == i) return;
        swap(&heap[i], &heap[largest]);
        i = largest;
    }
}

void insert(int key) { heap[n] = key; siftUp(n); n++; }

int extractMax(void) {
    int top = heap[0];
    heap[0] = heap[--n];
    siftDown(0);
    return top;
}

void show(void) { for (int i = 0; i < n; i++) printf("%d ", heap[i]); printf("\n"); }

int main(void) {
    int keys[] = {40, 70, 30, 90, 50, 80, 60};
    for (int i = 0; i < 7; i++) insert(keys[i]);
    printf("heap array: "); show();
    printf("extract: %d\n", extractMax());
    printf("heap array: "); show();
    printf("extract all: ");
    while (n > 0) printf("%d ", extractMax());
    printf("\n");
    return 0;
}

Output

heap array: 90 70 80 40 50 30 60 
extract: 90
heap array: 80 70 60 40 50 30 
extract all: 80 70 60 50 40 30

Try it Yourself

Building a heap in O(n)

Inserting n keys one by one costs O(n log n). Heapify does better: start from the last internal node (index n/2 − 1) and sift each node down, moving towards the root. Most nodes are near the bottom and sift down only a little, which adds up to O(n).

Heap sort

Build a max-heap from the array — O(n).
Repeatedly swap the root (maximum) with the last element of the heap, shrink the heap by one, and sift the new root down — n × O(log n).

Total O(n log n) in every case, using O(1) extra space. It is not stable.

#include <stdio.h>

void siftDown(int a[], int n, int i) {
    for (;;) {
        int big = i, l = 2 * i + 1, r = 2 * i + 2;
        if (l < n && a[l] > a[big]) big = l;
        if (r < n && a[r] > a[big]) big = r;
        if (big == i) return;
        int t = a[i]; a[i] = a[big]; a[big] = t;
        i = big;
    }
}

void heapSort(int a[], int n) {
    for (int i = n / 2 - 1; i >= 0; i--) siftDown(a, n, i);      // build max-heap
    for (int end = n - 1; end > 0; end--) {
        int t = a[0]; a[0] = a[end]; a[end] = t;                 // move max to the end
        siftDown(a, end, 0);                                     // fix the smaller heap
    }
}

int main(void) {
    int a[] = {12, 3, 45, 7, 23, 9, 31, 1};
    heapSort(a, 8);
    for (int i = 0; i < 8; i++) printf("%d ", a[i]);
    printf("\n");
    return 0;
}

Output

1 3 7 9 12 23 31 45

Try it Yourself

Heap operation costs

Operation	Cost
Find max (max-heap)	O(1)
Insert	O(log n)
Extract max	O(log n)
Build heap from n keys	O(n)
Heap sort	O(n log n)

Heaps are the standard way to implement priority queues — used in Dijkstra's shortest paths, Prim's MST, CPU scheduling and "top-k" problems.

Test yourself

4 questions · pick an answer to check it instantly

1
In a max-heap stored in an array, where is the largest element?
2
What is the parent of the element at index 9 (0-based)?
3
What is the time complexity of building a heap from n elements with bottom-up heapify?
4
Is [50, 30, 40, 35, 10] a valid max-heap?

#Stored in an array

#Insert: add at the end, then sift up

#Extract max: move the last key to the root, then sift down

#Building a heap in O(n)

#Heap sort

#Heap operation costs