Priority Queue with Unique Elements

To ensure that a priority queue contains only unique elements, you can use a combination of a priority queue and a set data structure. The set will keep track of the unique elements, while the priority queue will maintain the heap property based on the priority of the elements.

Here's an example of how you can implement a priority queue with unique elements:

1#include <iostream>
2#include <queue>
3#include <unordered_set>
4
5int main() {
6  std::priority_queue<int> pq;
7  std::unordered_set<int> uniqueElements;
8
9  auto insertElement = [&](int element) {
10    if (uniqueElements.insert(element).second) {
11      pq.push(element);
12    }
13  };
14
15  insertElement(10);
16  insertElement(30);
17  insertElement(20);
18  insertElement(30); // Duplicate not inserted
19  insertElement(40);
20
21  while (!pq.empty()) {
22    std::cout << pq.top() << " ";
23    pq.pop();
24  }
25}

In this example, we create a std::priority_queue<int> to store the elements and a std::unordered_set<int> to keep track of the unique elements.

We define a lambda function insertElement that takes an element as input. Inside the lambda function, we attempt to insert the element into the uniqueElements set using the insert() method. The insert() method returns a pair, where the second element is a boolean indicating whether the insertion was successful (i.e., the element was not already present in the set).

If the insertion into the set is successful, we push the element into the priority queue using pq.push(). This ensures that only unique elements are added to the priority queue.

When you run this code, it will output:

140 30 20 10

As you can see, the duplicate element 30 is not inserted into the priority queue.

By using a set to keep track of the unique elements, we can efficiently check if an element is already present before inserting it into the priority queue. The time complexity of insertion into both the set and the priority queue is O(log n), where n is the number of elements.

Note that using a set to maintain uniqueness adds some overhead compared to a regular priority queue, so use this approach only if maintaining uniqueness is a requirement for your specific use case.