Priority Queue with Stable Ordering

By default, the std::priority_queue in C++ does not guarantee stable ordering when elements have the same priority. This means that if you insert elements with equal priorities, the order in which they are retrieved from the queue may not necessarily match the order in which they were inserted.

However, if you need stable ordering in a priority queue, you can achieve this by including additional information in the comparison function to break ties when elements have the same priority.

Here's an example of how you can ensure stable ordering in a priority queue:

1#include <iostream>
2#include <queue>
3#include <vector>
4
5struct Element {
6  int value;
7  int priority;
8  int insertionOrder;
9};
10
11struct CompareElement {
12  bool operator()(const Element& e1,
13    const Element& e2) {
14    if (e1.priority == e2.priority) {
15      return e1.insertionOrder >
16        e2.insertionOrder;
17    }
18    return e1.priority < e2.priority;
19  }
20};
21
22int main() {
23  std::priority_queue<Element,
24    std::vector<Element>, CompareElement> pq;
25  int insertionOrder = 0;
26
27  auto insertElement = [&](int value,
28    int priority) {
29    pq.push({value, priority, insertionOrder++});
30  };
31
32  insertElement(10, 2);
33  insertElement(20, 1);
34  insertElement(30, 2);
35  insertElement(40, 1);
36
37  while (!pq.empty()) {
38    std::cout << pq.top().value << " (Priority: "
39      << pq.top().priority << ")\n";
40    pq.pop();
41  }
42}

In this example, we define a struct Element that represents an element with a value, a priority, and an additional field insertionOrder to keep track of the order in which elements are inserted.

We also define a custom comparator CompareElement that compares elements based on their priority. When the priorities are equal, the comparator uses the insertionOrder to determine the order. Elements with a lower insertionOrder value are considered to have a higher priority, ensuring stable ordering.

We create a priority queue of Element objects and define a lambda function insertElement that takes a value and a priority. Inside the lambda function, we create an Element object with the given value, priority, and the current insertionOrder, and push it into the priority queue. The insertionOrder is incremented after each insertion.

Finally, we insert elements into the priority queue using the insertElement lambda function and print the elements in the order they are retrieved from the queue.

The output of this code will be:

120 (Priority: 1)
240 (Priority: 1)
310 (Priority: 2)
430 (Priority: 2)

As you can see, the elements with the same priority (1 and 2) are retrieved in the order they were inserted, ensuring stable ordering.

By including additional information, such as the insertion order, in the comparison function, you can break ties and maintain stable ordering in a priority queue when elements have the same priority.