Heap / Priority Queue

Concept

A heap is a complete binary tree where every parent is >= its children (max-heap) or <= its children (min-heap). C++ priority_queue is a max-heap by default. It supports O(log n) push and pop, and O(1) access to the top (max/min) element. Heaps are the backbone of Dijkstra and greedy algorithms that need the current best element.

When to Use

  • ▸Dijkstra's algorithm (min-heap for closest unvisited node)
  • ▸Finding the k-th largest/smallest element
  • ▸Merging k sorted arrays
  • ▸Scheduling problems (always process highest priority task)
  • ▸Median maintenance (two heaps)

Intuition

A heap is stored as a flat array where node i has children at 2i+1 and 2i+2, and parent at (i-1)/2. Push: add at the end, bubble up by swapping with parent until heap property holds. Pop: swap root with last element, remove last, bubble down the new root. Building a heap from n elements is O(n) using bottom-up heapify — start from the last non-leaf and sift down each node. In contests, just use priority_queue and focus on the problem.

Complexity

Time
O(log n) push/pop, O(1) top, O(n) build heap
Space
O(n)

Template Code

cpp
#include<bits/stdc++.h>
using namespace std;

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    // --- Max-Heap (default priority_queue) ---
    priority_queue<int> maxpq;
    maxpq.push(3);
    maxpq.push(1);
    maxpq.push(5);
    maxpq.push(2);

    cout << "Max-heap: ";
    while(!maxpq.empty()){
        cout << maxpq.top() << " ";
        maxpq.pop();
    }
    cout << "\n";  // 5 3 2 1

    // --- Min-Heap ---
    priority_queue<int, vector<int>, greater<int>> minpq;
    minpq.push(3);
    minpq.push(1);
    minpq.push(5);
    minpq.push(2);

    cout << "Min-heap: ";
    while(!minpq.empty()){
        cout << minpq.top() << " ";
        minpq.pop();
    }
    cout << "\n";  // 1 2 3 5

    // --- Min-Heap of pairs (Dijkstra style) ---
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
    pq.push({5, 0});  // {distance, node}
    pq.push({2, 1});
    pq.push({8, 2});

    // Always gives smallest distance first
    int w = pq.top().first;   // 2
    int u = pq.top().second;  // 1
    pq.pop();

    // --- Build heap from array (using make_heap) ---
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++) cin >> v[i];

    // make_heap builds max-heap in O(n)
    make_heap(v.begin(), v.end());
    cout << "Max: " << v[0] << "\n";

    // push_heap / pop_heap maintain heap property
    v.push_back(10);
    push_heap(v.begin(), v.end());
    cout << "Max after push 10: " << v[0] << "\n";

    pop_heap(v.begin(), v.end());  // moves max to back
    int mx = v.back();
    v.pop_back();
    cout << "Popped: " << mx << "\n";

    // --- Heap sort ---
    sort_heap(v.begin(), v.end());
    for(int x : v) cout << x << " ";
    cout << "\n";

    return 0;
}

// Sample Input:
// 6
// 4 1 7 3 9 2
//
// Sample Output:
// Max-heap: 5 3 2 1
// Min-heap: 1 2 3 5
// Max: 9
// Max after push 10: 10
// Popped: 10
// 1 2 3 4 7 9