Heap and Heap Sort

Types of heaps

The rule is only between a parent and its children. Nothing is said about two siblings or about left against right — that is the difference from a BST.

Four properties

• Complete Binary Tree: all levels are completely filled except possibly the last level, which is filled from left to right
• Heap Property: the parent–child relationship follows the max-heap or min-heap rule
• Array Representation: heaps are typically implemented using arrays (vectors) for efficiency
• Height: O(log n) for n elements

For a node at index i

Example min-heap:

        10
       /  \
      15   20
     / \  / \
    30 40 50 60

Array: [10, 15, 20, 30, 40, 50, 60]
Index:  0   1   2   3   4   5   6

1 · The array and the index formulas

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
    public:
    vector<int> a;

    // Get parent index
    int parent(int i) {
        return (i - 1) / 2;
    }

    // Get left child index
    int left(int i) {
        return 2 * i + 1;
    }

    // Get right child index
    int right(int i) {
        return 2 * i + 2;
    }

    ...
};

The whole tree is one vector<int>. Parent and children are computed, not stored.

2 · getMin

// Get minimum element (root) - O(1)
int getMin() {
    return a[0];
}

The minimum of a min-heap is always at the root — index 0. O(1).

3 · insert — bubble up

// Insert element - O(log n)
void insert(int k) {
    // Add element at the end
    a.push_back(k);
    int ind = a.size() - 1;

    // Heapify up: bubble up the element
    while (ind > 0 && a[ind] < a[parent(ind)]) {
        swap(a[ind], a[parent(ind)]);
        ind = parent(ind);
    }
}

The new element goes to the end, so the tree stays complete. Then it rises while it is smaller than its parent — at most one swap per level.

4 · heapify — sift down

// Heapify down - O(log n)
void heapify(int i) {
    if (left(i) > a.size() - 1)
        return;

    // Find smallest among node and its children
    int j = left(i);
    if (right(i) < a.size() && a[right(i)] < a[left(i)])
        j = right(i);

    // If parent is greater than smallest child, swap and continue
    if (a[i] > a[j]) {
        swap(a[i], a[j]);
        heapify(j);
    }
}

Pick the smaller child — the right one only if it exists. If the node is bigger than it, swap and repeat one level down.

5 · extractMin

// Extract minimum element - O(log n)
int extractMin() {
    int root_value = getMin();

    // Replace root with last element
    swap(a[0], a[a.size() - 1]);
    a.pop_back();

    // Heapify down from root
    if (a.size() > 0)
        heapify(0);

    return root_value;
}

Moving the last element into the root keeps the tree complete; heapify then restores the order from the top.

6 · main

int main() {
    int n, x;
    cin >> n;
    MinHeap *heap = new MinHeap();

    // Insert n elements
    for (int i = 0; i < n; i++) {
        cin >> x;
        heap->insert(x);
    }

    // Extract all elements (sorted order)
    for (int i = 0; i < n; i++)
        cout << heap->extractMin() << " ";

    return 0;
}

Input

7
64 34 25 12 22 11 90

11 12 22 25 34 64 90

The whole program

Everything above in one file. Open it, put the input into stdin, and press Run.

#include <iostream>
#include <vector>

using namespace std;

class MinHeap {
    public:
    vector<int> a;

    // Get parent index
    int parent(int i) {
        return (i - 1) / 2;
    }

    // Get left child index
    int left(int i) {
        return 2 * i + 1;
    }

    // Get right child index
    int right(int i) {
        return 2 * i + 2;
    }

    // Get minimum element (root) - O(1)
    int getMin() {
        return a[0];
    }

    // Insert element - O(log n)
    void insert(int k) {
        // Add element at the end
        a.push_back(k);
        int ind = a.size() - 1;

        // Heapify up: bubble up the element
        while (ind > 0 && a[ind] < a[parent(ind)]) {
            swap(a[ind], a[parent(ind)]);
            ind = parent(ind);
        }
    }

    // Heapify down - O(log n)
    void heapify(int i) {
        if (left(i) > a.size() - 1)
            return;

        // Find smallest among node and its children
        int j = left(i);
        if (right(i) < a.size() && a[right(i)] < a[left(i)])
            j = right(i);

        // If parent is greater than smallest child, swap and continue
        if (a[i] > a[j]) {
            swap(a[i], a[j]);
            heapify(j);
        }
    }

    // Extract minimum element - O(log n)
    int extractMin() {
        int root_value = getMin();

        // Replace root with last element
        swap(a[0], a[a.size() - 1]);
        a.pop_back();

        // Heapify down from root
        if (a.size() > 0)
            heapify(0);

        return root_value;
    }
};

int main() {
    int n, x;
    cin >> n;
    MinHeap *heap = new MinHeap();

    // Insert n elements
    for (int i = 0; i < n; i++) {
        cin >> x;
        heap->insert(x);
    }

    // Extract all elements (sorted order)
    for (int i = 0; i < n; i++)
        cout << heap->extractMin() << " ";

    return 0;
}

1 · Insert — O(log n)

1. Add the element at the end of the array
2. Compare with its parent
3. If smaller than the parent (min-heap), swap
4. Continue until the heap property is satisfied

Example: insert 5 into [10, 15, 20, 30, 40]. It lands at index 5, whose parent is index 2 — the value 20.

Step 1: [10, 15, 20, 30, 40, 5]  — add at end
Step 2: [10, 15, 5, 30, 40, 20]  — swap with parent (20)
Step 3: [5, 15, 10, 30, 40, 20]  — swap with parent (10)

Two swaps — the heap has three levels, so it could never take more than two.

2 · Extract min — O(log n)

1. Save the root value (the minimum)
2. Replace the root with the last element
3. Remove the last element
4. Heapify down from the root

Example: extract min from [10, 15, 20, 30, 40, 50].

Step 1: save 10 (minimum)
Step 2: [50, 15, 20, 30, 40]  — replace root with last
Step 3: [15, 50, 20, 30, 40]  — heapify: swap 50 with 15
Step 4: [15, 30, 20, 50, 40]  — heapify: swap 50 with 30
Result: return 10, heap is [15, 30, 20, 50, 40]

At each step 50 goes to the smaller child: 15 rather than 20, then 30 rather than 40.

3 · Heapify — O(log n)

1. Compare the node with its children
2. Find the smallest among the node and its children
3. If the node is not the smallest, swap it with the smallest child
4. Recursively heapify the affected subtree

Insert 50, 30, 20, 15, 10, 8, 16

Insert 50:  [50]

Insert 30:  [50, 30]
            [30, 50]  — swap with parent (50)

Insert 20:  [30, 50, 20]
            [20, 50, 30]  — swap with parent (30)

Insert 15:  [20, 50, 30, 15]
            [20, 15, 30, 50]  — swap with parent (50)
            [15, 20, 30, 50]  — swap with parent (20)

Insert 10:  [15, 20, 30, 50, 10]
            [15, 10, 30, 50, 20]  — swap with parent (20)
            [10, 15, 30, 50, 20]  — swap with parent (15)

Insert 8:   [10, 15, 30, 50, 20, 8]
            [10, 15, 8, 50, 20, 30]  — swap with parent (30)
            [8, 15, 10, 50, 20, 30]  — swap with parent (10)

Insert 16:  [8, 15, 10, 50, 20, 30, 16]

Final heap: [8, 15, 10, 50, 20, 30, 16]

        8
       /  \
      15   10
     / \  / \
    50 20 30 16

Check the rule: every parent is smaller than its children. The array is not sorted — 50 comes before 20 — and it does not need to be.

Build, then extract

1. Build heap: insert all elements — O(n log n)
2. Extract all: extract min repeatedly — O(n log n)
3. Result: sorted array in ascending order

Example. Input: [64, 34, 25, 12, 22, 11, 90]

After building heap: [11, 22, 12, 64, 25, 34, 90]

Extract operations:
Extract: 11 → Heap: [12, 22, 34, 64, 25, 90]
Extract: 12 → Heap: [22, 25, 34, 64, 90]
Extract: 22 → Heap: [25, 64, 34, 90]
Extract: 25 → Heap: [34, 64, 90]
Extract: 34 → Heap: [64, 90]
Extract: 64 → Heap: [90]
Extract: 90 → Heap: []

Sorted: [11, 12, 22, 25, 34, 64, 90]

Each operation

Memory

• Vector storage: O(n) for n elements
• Recursion stack: O(log n) for the heapify operation
• Total: O(n)

1 · Priority queue

MinHeap pq;
pq.insert(5);  // Add task with priority 5
pq.insert(1);  // Add task with priority 1
pq.insert(3);  // Add task with priority 3

// Process in priority order (1, 3, 5)
while (!pq.a.empty()) {
    cout << pq.extractMin() << " ";
}

Tasks go in as 5, 1, 3 and come out as 1, 3, 5.

2 · Finding the k smallest elements

MinHeap heap;
// Insert all elements
for (int num : array)
    heap.insert(num);

// Extract k smallest
for (int i = 0; i < k; i++)
    cout << heap.extractMin() << " ";

3 · Heap sort

MinHeap heap;
// Insert all elements
for (int num : unsorted_array)
    heap.insert(num);

// Extract all (sorted)
vector<int> sorted;
while (!heap.a.empty())
    sorted.push_back(heap.extractMin());

4 · Merging k sorted arrays

• Insert the first element of each array into a min-heap
• Extract the minimum, insert the next element from the same array
• Continue until all elements are processed

Why this code is a good starting point

1. Simple and clean code
2. STL vector for dynamic size
3. Recursive heapify is easy to understand
4. Direct array access for efficiency
5. Compact implementation with the essential operations

1 · Add a size check

int getMin() {
    if (a.empty()) {
        throw runtime_error("Heap is empty");
    }
    return a[0];
}

2 · Add a build-heap method

void buildHeap(vector<int> arr) {
    a = arr;
    // Start from last non-leaf node
    for (int i = a.size() / 2 - 1; i >= 0; i--) {
        heapify(i);
    }
}

The last non-leaf node is at n / 2 − 1; everything after it is a leaf and already a heap.

3 · Add a print function

void printHeap() {
    for (int i = 0; i < a.size(); i++)
        cout << a[i] << " ";
    cout << endl;
}

Three comparisons flipped

class MaxHeap {
public:
    vector<int> a;

    int parent(int i) { return (i - 1) / 2; }
    int left(int i) { return 2 * i + 1; }
    int right(int i) { return 2 * i + 2; }

    int getMax() { return a[0]; }

    void insert(int k) {
        a.push_back(k);
        int ind = a.size() - 1;
        // Change: bubble up if GREATER than parent
        while (ind > 0 && a[ind] > a[parent(ind)]) {
            swap(a[ind], a[parent(ind)]);
            ind = parent(ind);
        }
    }

    void heapify(int i) {
        if (left(i) > a.size() - 1)
            return;
        int j = left(i);
        // Change: find LARGEST child
        if (right(i) < a.size() && a[right(i)] > a[left(i)])
            j = right(i);
        // Change: swap if parent is SMALLER
        if (a[i] < a[j]) {
            swap(a[i], a[j]);
            heapify(j);
        }
    }

    int extractMax() {
        int root_value = getMax();
        swap(a[0], a[a.size() - 1]);
        a.pop_back();
        if (a.size() > 0)
            heapify(0);
        return root_value;
    }
};

Input → process → output

7
64 34 25 12 22 11 90

Insert 64: [64]
Insert 34: [34, 64]
Insert 25: [25, 64, 34]
Insert 12: [12, 25, 34, 64]
Insert 22: [12, 22, 34, 64, 25]
Insert 11: [11, 22, 12, 64, 25, 34]
Insert 90: [11, 22, 12, 64, 25, 34, 90]

        11
       /  \
      22   12
     / \  / \
    64 25 34 90

11 12 22 25 34 64 90

Q1 · Why is heapify O(log n)?

At each step we compare and possibly swap with one child, moving down one level. The heap height is log n, so there are at most log n steps.

Q2 · Build heap — O(n) or O(n log n)?

• Inserting n elements one by one: O(n log n)
• Building from an array (heapify from the bottom): O(n) — more efficient

Q3 · Why use a heap for sorting?

• Guaranteed O(n log n) time
• In-place if implemented correctly
• No worst-case degradation like Quick Sort

Q4 · When to use a min-heap and when a max-heap?

• Min-Heap: find the smallest elements, sort in ascending order
• Max-Heap: find the largest elements, sort in descending order

Heap against the rest

Eight things to remember

1. A min-heap always has the minimum at the root — O(1) access
2. Insert and extract are O(log n)
3. Heapify maintains the heap property by comparing with the children
4. A complete binary tree stored in an array — space efficient
5. Heap sort achieves O(n log n) by repeated extract operations
6. Parent–child relationships are given by simple formulas
7. No pointer manipulation — array indices handle the structure
8. Perfect for a priority queue

Try these

1. Find the k-th smallest element in an array
2. Merge k sorted arrays
3. Find the median in a data stream
4. Sort a nearly sorted array
5. Connect n ropes with minimum cost
6. Find the k largest elements in an array
7. Implement a heap using only insert and extractMin

Problem to topic