Priority Queues using std::priority_queue

# Priority Queue with Unique Elements

## How can I ensure that a priority queue contains only 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:

#include <iostream>
#include <queue>
#include <unordered_set>

int main() {
std::priority_queue<int> pq;
std::unordered_set<int> uniqueElements;

auto insertElement = [&](int element) {
if (uniqueElements.insert(element).second) {
pq.push(element);
}
};

insertElement(10);
insertElement(30);
insertElement(20);
insertElement(30); // Duplicate not inserted
insertElement(40);

while (!pq.empty()) {
std::cout << pq.top() << " ";
pq.pop();
}
}

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:

40 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.

This Question is from the Lesson:

### Priority Queues using std::priority_queue

Learn how to access objects based on their importance, and how to customise how that priority is determined

Answers to questions are automatically generated and may not have been reviewed.

This Question is from the Lesson:

### Priority Queues using std::priority_queue

Learn how to access objects based on their importance, and how to customise how that priority is determined

Part of the course:

## Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.

Free, unlimited access

### This course includes:

• 124 Lessons
• 550+ Code Samples
• 96% Positive Reviews
• Regularly Updated
• Help and FAQ
Free, Unlimited Access

### Professional C++

Comprehensive course covering advanced concepts, and how to use them on large-scale projects.