Heap Operations

make_heap — build a heap

• make_heap(first, last) rearranges [first, last) into a max-heap.
• Afterward, *first (or v.front()) is the largest.
• **Real-life:** take today’s emergency tickets and arrange so the hottest issue is on top.

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

int main() {
    vector<int> v = {3, 1, 4, 2};
    make_heap(v.begin(), v.end());
    cout << v.front() << "\n"; // 4
    return 0;
}

push_heap — add then sift up

• 1) v.push_back(x) — new item at the end.
• 2) push_heap(v.begin(), v.end()) — restore the heap property.
• **Real-life:** a new patient arrives; add to the board, then bubble to the right urgency slot.

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

int main() {
    vector<int> v = {3, 1, 4, 2};
    make_heap(v.begin(), v.end());
    v.push_back(9);
    push_heap(v.begin(), v.end());
    cout << v.front() << "\n"; // 9
    return 0;
}

pop_heap — remove the top

• pop_heap swaps the top to the **end** and re-heaps the rest.
• Then v.pop_back() actually removes that former top.
• **Real-life:** serve the most urgent ticket; move it aside, then reorganize who is next.

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

int main() {
    vector<int> v = {3, 1, 4, 2};
    make_heap(v.begin(), v.end());
    pop_heap(v.begin(), v.end());
    int top = v.back();
    v.pop_back();
    cout << top << "\n";          // 4
    cout << v.front() << "\n";    // next largest among remaining
    return 0;
}

sort_heap and is_heap

• sort_heap turns a **valid heap** into a **sorted** ascending range (destroys heap order).
• is_heap checks whether a range is already a heap.
• **Real-life:** after triage is done, sort_heap is like printing a final ranked list from the board.

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

int main() {
    vector<int> v = {3, 1, 4, 2};
    make_heap(v.begin(), v.end());
    cout << boolalpha << is_heap(v.begin(), v.end()) << "\n"; // true
    sort_heap(v.begin(), v.end());
    for (int x : v) cout << x << " ";
    cout << "\n"; // 1 2 3 4
    return 0;
}

Min-heap with a comparator

• Pass greater{} (or a lambda) as the third argument to heap algorithms.
• Then front() is the **smallest**.
• **Real-life:** next-event simulation — earliest timestamp should be on top.

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

int main() {
    vector<int> v = {3, 1, 4, 2};
    make_heap(v.begin(), v.end(), greater<int>{});
    cout << v.front() << "\n"; // 1
    return 0;
}

Real-life examples

• Heaps model “always handle the extreme next”.

Heap applications

• Use heap ops when you repeatedly need the current max/min from a changing set.