Implement Max Heap

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

Implement Max Heap

A max-heap is a complete binary tree stored as an array where every parent is ≥ its children. The root is always the maximum element.

Array index relationships for node at index i:

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

Note

Max Heap is identical to Min Heap — the only difference is the comparison direction. In heapify up, you bubble toward the root when the child is larger than the parent. In heapify down, you swap with the largest child.

Core Operations

Operation	Time	How
`insert(val)`	`O(log n)`	Append to end, heapify up
`extractMax()`	`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: Max-heap is identical to min-heap — the only difference is which direction comparisons go. If you already understand min-heap, you already understand max-heap.

Approach:

Flip every comparison: heapify up swaps when child > parent (instead of child < parent), heapify down picks the largest child to swap with (instead of the smallest).
All other mechanics stay exactly the same — the array structure, index formulas, insert procedure, and extract procedure are unchanged.

Full Implementation

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

class MaxHeap {
    vector<int> heap;

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

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

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

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

    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:
// MaxHeap h;
// h.insert(5); h.insert(3); h.insert(8); h.insert(1);
// h.extractMax(); // 8
// h.peek();       // 5