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++: 

 

 

 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; 

 

 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.