Skip to main content

5. The Heap in Practice: The C++ Standard Template Library (STL)

While understanding how to build Heap Sort from scratch is crucial for algorithmic knowledge, in modern C++, we often leverage the powerful abstractions provided by the Standard Template Library (STL). The concepts of a heap are primarily exposed through std::priority_queue.

std::priority_queue: A Ready-to-Use Heap

The C++ STL provides a container adapter called std::priority_queue that is an implementation of a Heap.

  • Default Behavior: By default, std::priority_queue<int> is a Max-Heap. This means that when you call top(), it returns the largest element, and when you pop(), it removes the largest element while maintaining the heap property.

  • Core Operations:

    • push(): Adds an element to the queue (heap). This internally performs a sift-up operation. Complexity: O(log n).

    • pop(): Removes the top element. Complexity: O(log n).

    • top(): Returns a reference to the top element without removing it. Complexity: O(1).

Working with Custom Data Types

What happens if we want to create a priority queue of custom objects, like a struct for patients in a hospital?

struct Patient {
    std::string name;
    int triage_level; // Level 1 is highest priority
};

// This will cause a compile error!
std::priority_queue<Patient> er_queue;

The compiler doesn't know how to compare two Patient objects. To solve this, we must provide our own custom comparison logic.

Custom Comparators: Functors and Lambda Expressions

We can tell std::priority_queue how to order our custom types using a custom comparator. There are two common ways to do this in modern C++:

  1. Functor (Function Object): A struct or class that overloads the function call operator operator(). The priority_queue will create an object of this type and use its operator() to compare elements. This is a powerful, stateful way to define comparison logic.

  2. Lambda Expression: An inline, anonymous function that can be defined on the spot. Lambdas are often more concise and readable for simple, stateless comparison logic. They are commonly used with algorithms like std::sort.

By providing these comparators, we can leverage the highly optimized and safe implementation of a heap provided by the STL for any data type we need.

 

Back to top