Implement Min Heap

Build a min-heap from scratch — insert, extract-min, and peek with heapify up/down.

Implement Min Heap

A min-heap is a complete binary tree stored as an array where every parent is ≤ its children. The root is always the minimum element.

Array index relationships for node at index i:

Parent: (i - 1) / 2
Left child: 2i + 1
Right child: 2i + 2

Note

Two operations maintain the heap property: heapify up (used after insert — bubble new element toward root) and heapify down (used after extract — sink the replacement down to its correct level).

Core Operations

Operation	Time	How
`insert(val)`	`O(log n)`	Append to end, heapify up
`extractMin()`	`O(log n)`	Swap root with last, remove last, heapify down
`peek()`	`O(1)`	Return `arr[0]`
`size()`	`O(1)`	Return array length

How to Think About It

Intuition: An array can represent a complete binary tree using index math alone. The challenge is keeping the "smallest at root" rule intact after every insert and delete.

Approach:

On insert: append to the end (tree stays complete), then bubble the new element up — compare with its parent, swap if smaller, repeat until it settles.
On extract: the root is gone, so move the last element to position 0 (tree stays complete), then sink it down — compare with both children, swap with the smaller one, repeat until settled.
You only need these two helpers (heapifyUp and heapifyDown) — every other operation is trivial once they exist.

Full Implementation

#include <vector>
#include <stdexcept>
using namespace std;

class MinHeap {
    vector<int> heap;

    void heapifyUp(int i) {
        while (i > 0) {
            int parent = (i - 1) / 2;
            if (heap[parent] > heap[i]) {
                swap(heap[parent], heap[i]);
                i = parent;
            } else break;
        }
    }

    void heapifyDown(int i) {
        int n = heap.size();
        while (true) {
            int smallest = i;
            int left  = 2 * i + 1;
            int right = 2 * i + 2;
            if (left  < n && heap[left]  < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right;
            if (smallest == i) break;
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }

public:
    void insert(int val) {
        heap.push_back(val);
        heapifyUp(heap.size() - 1);
    }

    int extractMin() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        int minVal = heap[0];
        heap[0] = heap.back();
        heap.pop_back();
        if (!heap.empty()) heapifyDown(0);
        return minVal;
    }

    int peek() const {
        if (heap.empty()) throw runtime_error("Heap is empty");
        return heap[0];
    }

    int size() const { return heap.size(); }
    bool empty() const { return heap.empty(); }
};

// Usage:
// MinHeap h;
// h.insert(5); h.insert(3); h.insert(8); h.insert(1);
// h.extractMin(); // 1
// h.peek();       // 3