# 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?
```c++
struct Patient {
std::string name;
int triage_level; // Level 1 is highest priority
};
// This will cause a compile error!
std::priority_queue 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.
```c++
struct ComparePatients {
bool operator()(const Patient& a, const Patient& b) {
// Because priority_queue is a Max-Heap, it puts the "larger"
// element on top. We want level 1 to be the highest priority,
// so we tell the queue that 'a' is "less than" 'b' if its
// triage level is numerically greater.
return a.triage_level > b.triage_level;
}
};
// Usage:
std::priority_queue, ComparePatients> er_queue;
```
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.
```c++
auto compare_lambda = [](const Patient& a, const Patient& b) {
return a.triage_level > b.triage_level;
};
// Usage with priority_queue is slightly more verbose
std::priority_queue, decltype(compare_lambda)> er_queue(compare_lambda);
```
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.