Priority Queue
Lesson 12 of 23 in Coddy's C++ - Standard Template Library course.
In C++, we also have the data structure called priority queue. The priority queue provides us with a special functionality that the queue doesn't have, in which each element is associated with a priority value and the elements are served based on their priority.
A basic priority queue is designed such that the first element of the queue is the greatest of all the elements, and the rest are sorted in a descending order.
priority_queue<dataType> queueNameFirst, we need to include the priority queue header file at the top of our C++ file.
We create the priority queue as the other containers already learned.
priority_queue<int> integers;Next, we use the push() method to add new elements to the queue. The element is added and if it's greater than all the elements, it will be stored first. If it's smaller than all the other elements it will be stored last, and so on.
integers.push(5); // integers = {5)For outputting the elements we use the top() method like the stack. It outputs the element with the highest priority, in the case with integers, it will output the largest number.
integers.push(100); // integers = {100, 5}
integers.push(10); // integers = {100, 10, 5}
integers.push(3); // integers = {100, 10, 5, 3}
cout << integers.top();Output:
100We also remove elements exactly like with the stack, with the pop() method. It removes the element on the top, the element with the highest priority. In the case with numbers the largest one.
integers.pop(); // integers = {10, 5, 3}
cout << integers.top();Output:
10We can change the priority of the queue based on which the elements are sorted. For example, we can declare a priority queue that sorts integers in an ascending order like below:
priority_queue<int, vector<int>, greater<int> > integers;In this queue, when elements are inserted they are sorted in an ascending order. When we would like to display the top element, or remove it using the pop() method, the smallest number will be displayed or removed.
For now, don't bother about using the priority queue in a different way and changing the priority. Only remember that this data structure is available to our usage so we can sort elements based on some kind of priority
Priority Queue Methods
| Method | Funcitonality |
size() | Returns the number of elements of the queue |
empty() | Returns true if the queue is empty, false otherwise |
swap() | Swaps the contents of one queue, with another |
Challenge
EasyGiven a number N from input. In the next N lines you'll be given one number. Using a priority queue. Output the entered numbers from greatest to smallest (descending order).
Input
5
10
50
20
40
30Output
50 40 30 20 10Try it yourself
#include <queue>
#include <iostream
using namespace std;
int main()
{
// Enter your code here
return 0;
}