C++ Algorithm Heap | "Heap Algorithm" Guide

STL heap algorithms treat a random-access range as a binary heap in the underlying container—usually a vector. By default you get a max-heap (front() is the largest). push_heap / pop_heap maintain the heap property in O(log n) per operation; make_heap is O(n). This is the same structure std::priority_queue uses internally; the free functions are useful when you need custom storage or partial heap operations without an extra wrapper.

Heap algorithm

Max heap (default operator<): the root v[0] is the maximum. pop_heap moves the max to v[end-1] and shrinks the logical heap; you typically follow with pop_back() to remove it from the vector.

#include <algorithm>
#include <vector>

std::vector<int> v = {3, 1, 4, 1, 5};

// Create heap
std::make_heap(v.begin(), v.end());

// Maximum value
std::cout << v.front() << std::endl;  // 5

Basic usage

After make_heap, use push_heap after push_back to insert, and pop_heap before pop_back to extract the extremum. Always pass the same comparator to every heap call on that range.

#include <algorithm>

std::vector<int> v = {3, 1, 4, 1, 5};

// Create heap
std::make_heap(v.begin(), v.end());

// Remove maximum value
std::pop_heap(v.begin(), v.end());
v.pop_back();

// Add value
v.push_back(9);
std::push_heap(v.begin(), v.end());

Practical Examples

Example 1: Max Heap

#include <algorithm>
#include <vector>

int main() {
    std::vector<int> heap;
    
    // Add elements
    for (int x : {3, 1, 4, 1, 5, 9, 2, 6}) {
        heap.push_back(x);
        std::push_heap(heap.begin(), heap.end());
    }
    
    // Remove elements from the maximum
    while (!heap.empty()) {
        std::cout << heap.front() << " ";
        std::pop_heap(heap.begin(), heap.end());
        heap.pop_back();
    }
    // 9 6 5 4 3 2 1 1
}

Example 2: Min Heap

#include <algorithm>
#include <vector>
#include <functional>

int main() {
    std::vector<int> heap = {3, 1, 4, 1, 5};
    
    // Min heap
    std::make_heap(heap.begin(), heap.end(), std::greater<>());
    
    std::cout << "Minimum: " << heap.front() << std::endl;  // 1
}

Example 3: Top k Elements

#include <algorithm>
#include <vector>

std::vector<int> topK(const std::vector<int>& data, size_t k) {
    std::vector<int> heap;
    
    for (int x : data) {
        if (heap.size() < k) {
            heap.push_back(x);
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        } else if (x > heap.front()) {
            std::pop_heap(heap.begin(), heap.end(), std::greater<>());
            heap.back() = x;
            std::push_heap(heap.begin(), heap.end(), std::greater<>());
        }
    }
    
    std::sort_heap(heap.begin(), heap.end(), std::greater<>());
    return heap;
}

int main() {
    std::vector<int> data = {3, 1, 4, 1, 5, 9, 2, 6, 5, 3};
    auto top3 = topK(data, 3);
    
    for (int x : top3) {
        std::cout << x << " ";  // 9 6 5
    }
}

Example 4: Heap Sort

#include <algorithm>

int main() {
    std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
    
    // Create heap
    std::make_heap(v.begin(), v.end());
    
    // Heap sort
    std::sort_heap(v.begin(), v.end());
    
    for (int x : v) {
        std::cout << x << " ";  // 1 1 2 3 4 5 6 9
    }
}

Heap Operations

// Create heap
std::make_heap(begin, end)

// Add element
v.push_back(value);
std::push_heap(begin, end)

// Remove element
std::pop_heap(begin, end)
v.pop_back()

// Heap sort
std::sort_heap(begin, end)

// Check if heap
bool isHeap = std::is_heap(begin, end)

Common Issues

Issue 1: Heap Property

std::vector<int> v = {3, 1, 4, 1, 5};

// ❌ Not a heap
// std::pop_heap(v.begin(), v.end());  // Undefined behavior

// ✅ After creating a heap
std::make_heap(v.begin(), v.end());
std::pop_heap(v.begin(), v.end());

Issue 2: push_heap Order

std::vector<int> heap = {3, 1, 4};
std::make_heap(heap.begin(), heap.end());

// ❌ Incorrect order
// std::push_heap(heap.begin(), heap.end());
// heap.push_back(5);  // Added too late

// ✅ Correct order
heap.push_back(5);
std::push_heap(heap.begin(), heap.end());

Issue 3: pop_heap Order

std::vector<int> heap = {5, 4, 3, 1, 1};

// ✅ Correct order
std::pop_heap(heap.begin(), heap.end());  // Move max value to the end
heap.pop_back();  // Remove it

// ❌ Incorrect order
// heap.pop_back();
// std::pop_heap(heap.begin(), heap.end());

Issue 4: Comparison Function

// Max heap (default)
std::make_heap(v.begin(), v.end());

// Min heap
std::make_heap(v.begin(), v.end(), std::greater<>());

// Use the same comparison function for all heap operations
std::push_heap(v.begin(), v.end(), std::greater<>());
std::pop_heap(v.begin(), v.end(), std::greater<>());

priority_queue vs Heap

// priority_queue: Wrapper
std::priority_queue<int> pq;
pq.push(3);
pq.push(1);
pq.push(4);
std::cout << pq.top() << std::endl;  // 4

// Heap algorithms: Direct control
std::vector<int> heap;
heap.push_back(3);
std::push_heap(heap.begin(), heap.end());
heap.push_back(1);
std::push_heap(heap.begin(), heap.end());
std::cout << heap.front() << std::endl;  // 4

FAQ

Q1: What is a heap?

A: A max/min heap data structure.

Q2: What does make_heap do?

A: Converts a vector into a heap.

Q3: What does push_heap do?

A: Adds an element to the heap.

Q4: What does pop_heap do?

A: Removes the maximum value (moves it to the end).

Q5: What is priority_queue?

A: A wrapper for heaps. Convenient to use.

Q6: Any learning resources?

A:

• “Introduction to Algorithms”
• “Effective STL”
• cppreference.com

---

Related Posts (Internal Links)

Here are other posts related to this topic:

• C++ STL algorithms — English series hub
• C++ Algorithm Numeric | “Numeric Algorithm” Guide
• C++ Algorithm Reverse | “Reverse Algorithm” Guide
• C++ Algorithm Count | “Count Algorithm” Guide

Practical Tips

Here are tips you can apply directly in real-world scenarios.

Debugging Tips

• If an issue arises, first check compiler warnings
• Reproduce the issue with a simple test case

Performance Tips

• Avoid optimizing without profiling
• Set measurable performance metrics first

Code Review Tips

• Preemptively address common review comments
• Follow your team’s coding conventions

---

Practical Checklist

Use this checklist to ensure proper application of these concepts in real-world scenarios.

Before Writing Code

• Is this technique the best solution for the current problem?
• Can your team understand and maintain this code?
• Does it meet performance requirements?

While Writing Code

• Have you resolved all compiler warnings?
• Have you considered edge cases?
• Is error handling appropriate?

During Code Review

• Is the intent of the code clear?
• Are there sufficient test cases?
• Is the code well-documented?

Use this checklist to minimize mistakes and improve code quality.

---

Keywords Covered in This Post (Related Search Terms)

Search for terms like C++, algorithm, heap, priority-queue, STL to find more resources related to this post.