The core reason for my re-implementing the standard containers is the Priority Queue (or namely Max Heap). It combines algorithms and fundamental data structures to create a sophisticated yet highly efficient data structure. My current focus on reinventing these containers has temporarily paused here. Similar containers, like flat_set, are slated for release in C++23. When they become available, I plan to continue this series by attempting to re-implement them.

Description

A priority queue is a container adapter offering constant time access to the largest (by default) element, albeit at the cost of logarithmic time insertion and extraction. It adheres to two principal characteristics.

Structure Property

A typical std::priority_queue leverages a binary heap as its core data structure. A binary heap manifests as a complete binary tree, wherein all levels, barring potentially the last, are fully populated, with all nodes shifted as left as possible.

Order Property

In a max heap, the value of each node is std::less<T> than the value of its parent. The largest element is at the root.

  • The left child resides at index 2i + 1.
  • The right child is located at index 2i + 2.
  • The parent is found at index (i - 1)/2 (integer division).

Thus, the parent and its children are ordered from left to right in the vector.

Build A Heap

The priority queue is built upon a key function:

  • heapify: This function upholds the heap attributes for the subtree rooted at index by executing swaps and moving down (left → right, parent → children) through the vector.

Drawing upon heapify, three auxiliary heap functions are devised:

  • make_heap: Transforms a vector into a heap, proceeding backwards (right → left) from the vector’s midpoint to its front.
  • pop_heap: Swaps the front (max) element with the last, followed by heapifying the vector without the swapped last element.
  • push_heap: Swaps and move from the end to the front (right → left, child → parent) to restore the heap properties.

Code

#include <iostream>
#include <vector>

template <typename T,
          typename Container = std::vector<T>,
          typename Compare   = std::less<T>>
class PriorityQueue
{
  public:
  PriorityQueue()
  {
    make_heap(0, container.size() - 1, 0);
  }

  T& top()
  {
    return container.front();
  }

  void push(const T& value)
  {
    container.push_back(value);
    push_heap(0, container.size() - 1);
  }

  void pop()
  {
    if(container.empty())
    {
      return;
    }
    pop_heap();
    container.pop_back();
  }

  private:
  Container container;
  Compare   compare;

 //restores the heap property in a subtree rooted at a specified node index.
// It performs the necessary swaps moving down the heap until the heap property is restored.
  void heapify(size_t first, size_t last, size_t index)
  {
    const auto size    = last - first + 1;
    auto       left    = 2 * index + 1;
    auto       right   = 2 * index + 2;
    auto       largest = index;

    if(left < size && compare(container[largest], container[left]))
    {
      largest = left;
    }
    if(right < size && compare(container[largest], container[right]))
    {
      largest = right;
    }
    if(largest != index)
    {
      std::swap(container[index], container[largest]);
      heapify(first, last, largest);
    }
  }
 //builds a (max) heap from an unsorted range of elements.
// The loop starts from the last non-leaf node (first + (size / 2) - 1) 
// and moves towards the root node (first), calling heapify for each node along the way.
  void make_heap(size_t first, size_t last, size_t index)
  {
    const auto size = last - first + 1;
    for(int i = size / 2 - 1; i >= 0; i--)    // start from the middle node!
    {
      heapify(first, last, first + i);
    }
  }
// swaps the top element with the last element, removes the last element
// (which was previously the top element), and then calls heapify to restore the heap property.
  void pop_heap()
  {
    if(container.empty())
    {
      return;
    }
    std::swap(container.front(), container.back());
    heapify(0, container.size() - 2, 0);    // reconstruct the heap, excluding the last element
  }
// ensures the heap property is maintained after a new element has been inserted. 
//It performs the necessary swaps moving up the heap until the heap property is restored.
  void push_heap(size_t first, size_t last)
  {
    auto index  = last;
    auto parent = first + (last - 1) / 2;

    while(index > first && compare(container[parent], container[index]))
    {
      std::swap(container[index], container[parent]);
      index  = parent;
      parent = first + (index - 1) / 2;
    }
  }
};

int main()
{
    PriorityQueue<int> pq;
    pq.push(10);
    pq.push(20);
    pq.push(15);
    std::cout << pq.top() << std::endl;  // Output: 20
    pq.pop();
    std::cout << pq.top() << std::endl;  // Output: 15
    pq.pop();
    std::cout << pq.top() << std::endl;  // Output: 10
  return 0;
}