CppHow-ToBeginner · 3 min read

How to Implement Heap in C++: Syntax and Example

In C++, you can implement a heap using the std::make_heap, std::push_heap, and std::pop_heap functions from the STL. These functions work on a vector or array to maintain the heap property efficiently.

📐

Syntax

The main functions to implement a heap in C++ are:

std::make_heap(begin, end): Converts a range into a heap.
std::push_heap(begin, end): Adds a new element to the heap.
std::pop_heap(begin, end): Removes the top element from the heap.

These functions work on random-access containers like std::vector and require the range to be a valid heap before pushing or popping.

cpp

std::make_heap(container.begin(), container.end());
std::push_heap(container.begin(), container.end());
std::pop_heap(container.begin(), container.end());

💻

Example

This example shows how to create a max-heap, add elements, and remove the top element using STL heap functions.

cpp

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::vector<int> heap = {10, 20, 30, 5, 15};

    // Create a max heap from the vector
    std::make_heap(heap.begin(), heap.end());

    std::cout << "Initial max heap: ";
    for (int n : heap) std::cout << n << ' ';
    std::cout << '\n';

    // Add a new element
    heap.push_back(40);
    std::push_heap(heap.begin(), heap.end());

    std::cout << "After adding 40: ";
    for (int n : heap) std::cout << n << ' ';
    std::cout << '\n';

    // Remove the top element
    std::pop_heap(heap.begin(), heap.end());
    int top = heap.back();
    heap.pop_back();

    std::cout << "After removing top element (" << top << "): ";
    for (int n : heap) std::cout << n << ' ';
    std::cout << '\n';

    return 0;
}

Output

Initial max heap: 30 20 10 5 15 After adding 40: 40 30 10 5 15 20 After removing top element (40): 30 20 10 5 15

⚠️

Common Pitfalls

Common mistakes when implementing heaps in C++ include:

Not calling std::make_heap before using push_heap or pop_heap, which requires the container to already be a heap.
Forgetting to actually remove the element after pop_heap (it only moves the top element to the end).
Using heap functions on containers that do not support random access iterators.

cpp

#include <vector>
#include <algorithm>

// Wrong: Using push_heap without make_heap
std::vector<int> v = {1, 3, 2};
// std::push_heap(v.begin(), v.end()); // Undefined behavior if not a heap

// Right:
std::make_heap(v.begin(), v.end());
v.push_back(4);
std::push_heap(v.begin(), v.end());

📊

Quick Reference

Summary of STL heap functions:

Function	Purpose	Notes
std::make_heap(begin, end)	Builds a heap from a range	Call once before push/pop operations
std::push_heap(begin, end)	Adds last element to the heap	Container must already be a heap
std::pop_heap(begin, end)	Moves top element to end	Remove element from container after call
std::sort_heap(begin, end)	Sorts the heap into ascending order	Optional to get sorted data

✅

Key Takeaways

Use std::make_heap to build a heap from an unsorted container before other heap operations.

Use std::push_heap to add elements while maintaining heap property.

Use std::pop_heap to remove the top element, then erase it from the container.

Heap functions require random-access containers like std::vector.

Remember pop_heap only moves the top element; you must remove it manually.