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.
   

   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<Patient, std::vector<Patient>, 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.
   

   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<Patient, std::vector<Patient>, 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.