Heap

📚 Table of Contents

• What Is a Heap
• Heapify Up vs Down
• Ways to Build a Heap
• Min Heap Code
• Max Heap Code
• Heap using STL

A heap is a special tree-based data structure that satisfies the heap property. It is commonly used to implement priority queues, heapsort, and in many greedy algorithms like Dijkstra’s and Prim’s.

What Is a Heap?

A heap is a complete binary tree with a specific ordering property:

• Min-Heap: Each parent is less than or equal to its children.
• Max-Heap: Each parent is greater than or equal to its children.

Internally, a heap is usually implemented using an array for memory efficiency.

Parent and Child Indexes (0-based):

• parent(i) = (i – 1) / 2
• left(i) = 2 * i + 1
• right(i) = 2 * i + 2

Heapify Up vs Heapify Down

Heapify Up

Used when inserting a new element:

• Compare the newly added element with its parent.
• If it violates the heap property, swap up.
• Continue until the root or no violation.

Use case: insert(x)
Time complexity: O(log n)

Heapify Down

Used when removing the root:

• Replace root with the last element.
• Compare with children.
• Swap with the smaller/larger child.
• Continue until the leaf.

Use case: remove(), buildHeap()
Time complexity: O(log n)

Ways to Build a Heap

Method 1: Insert Elements One by One

As we have inserted a new element in heap and it can violate the heap property, so we will have heapify up so it goes to its right position.

for each element:
    insert(heap, element)  // uses heapify-up

Time complexity: O(n log n)

Method 2: Bottom-Up Heapify (Efficient)

🌲 Why Start from Last Non-Leaf Node?

A heap is a complete binary tree, so it has a very structured shape:

• Level 0: 1 node
• Level 1: 2 nodes
• Level 2: 4 nodes
• Level 3: 8 nodes
• Level 4: 16 nodes
• Level 5: 32 nodes

Notice that most of the nodes lie in the bottom levels. In fact, more than half the nodes are leaves or near the leaves. This matters because:

• Leaf nodes don’t need heapifying — they have no children.
• Only non-leaf nodes need to perform heapifyDown().

The last non-leaf node is at index n/2 - 1 (in 0-based arrays), and all nodes after that are leaves. So when we build the heap bottom-up, we can skip nearly half the nodes.

This is the key reason why bottom-up heap construction is faster — it avoids unnecessary work on leaves and does minimal work on near-leaves.

for i = n/2 - 1 down to 0:
    heapifyDown(array, i)

Time complexity: O(n)

📊 Heap Operations & Complexities

Operation	Time Complexity	Description
Insert (heapify-up)	O(log n)	New node may go to root
Get min/max	O(1)	Always at root
Remove min/max	O(log n)	Root replaced and heapified down
Build via inserts	O(n log n)	Repeated insertions
Build via heapify	O(n)	Bottom-up optimization
Replace root	O(log n)	Pop + insert combined

✅ Why Is Building Heap in O(n) Counterintuitive?

It seems counterintuitive because:

• Each heapifyDown() call can take up to log n time.
• If we do this for n/2 nodes, it feels like O(n log n).

But here’s the reality:

• Lower levels of the tree contain most of the nodes.
• These nodes require very little heapifying.
• Top levels have few nodes but may require more effort.

Work Analysis Table

Level	Nodes (2^d)	Work per Node (H – d)	Total Work
0	1	H	H
1	2	H – 1	2(H – 1)
2	4	H – 2	4(H – 2)
…	…	…	…
H	2^H	0	0

💻 Min Heap Code

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

class MinHeap {
private:
    vector<int> heap;

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

    void heapifyDown(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) { // range check
            int smallest = i;
            // left or right can be smallest
            int left = 2 * i + 1;
            int right = 2 * i + 2;

             // check which is smalles
            if (left < n && heap[left] < heap[smallest]) smallest = left;
            if (right < n && heap[right] < heap[smallest]) smallest = right;

            // parent itself is smallest, doesn't need to anything
            if (smallest == i) break;
            // otherwise move to correct pos, do for new parent
            swap(heap[i], heap[smallest]);
            i = smallest;
        }
    }

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

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

    void removeMin() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        // last element to front , reduce size, heapify down
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    void buildHeap(const vector<int>& arr) {
        heap = arr;
        //start from last non leaf
        for (int i = heap.size() / 2 - 1; i >= 0; --i) {
            heapifyDown(i);
        }
    }

    void print() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }
};

Max Heap Code

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

class MaxHeap {
private:
    vector<int> heap;

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

    void heapifyDown(int i) {
        int n = heap.size();
        while (2 * i + 1 < n) {
            int largest = i;
            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 getMax() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        return heap[0];
    }

    void removeMax() {
        if (heap.empty()) throw runtime_error("Heap is empty");
        heap[0] = heap.back();
        heap.pop_back();
        heapifyDown(0);
    }

    void buildHeap(const vector<int>& arr) {
        heap = arr;
        for (int i = heap.size() / 2 - 1; i >= 0; --i) {
            heapifyDown(i);
        }
    }

    void print() {
        for (int val : heap) cout << val << " ";
        cout << endl;
    }
};

Max Heap Vs Min Heap

< becomes > in heapifyUp and heapifyDown

Method names change from getMin() → getMax(), etc.

Max Heap Using Stl

#include <iostream>
#include <queue>
using namespace std;

int main() {
    priority_queue<int> maxHeap;

    // Insert elements
    maxHeap.push(10);
    maxHeap.push(30);
    maxHeap.push(20);
    maxHeap.push(5);

    // Access top element (maximum)
    cout << "Max Element: " << maxHeap.top() << endl;

    // Pop all elements
    cout << "Elements in maxHeap order: ";
    while (!maxHeap.empty()) {
        cout << maxHeap.top() << " ";
        maxHeap.pop();
    }
    cout << endl;

    return 0;
}

Min Heap using Stl

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

int main() {
    // Option 1: Use greater<int> as comparator
    priority_queue<int, vector<int>, greater<int>> minHeap;

    // Insert elements
    minHeap.push(10);
    minHeap.push(30);
    minHeap.push(20);
    minHeap.push(5);

    // Access top element (minimum)
    cout << "Min Element: " << minHeap.top() << endl;

    // Pop all elements
    cout << "Elements in minHeap order: ";
    while (!minHeap.empty()) {
        cout << minHeap.top() << " ";
        minHeap.pop();
    }
    cout << endl;

    return 0;
}