Priority Queue

A priority queue is a generalization of both the stack and queue. The difference is in the method of selecting which item to next pop off the data structure. A priority queue usually assigns a number to each item (the priority) and the item with the highest number (priority) is the next to come off. A priority queue that acts like a stack assigns the highest priority to new elements and the queue does exactly the opposite.

The priority queue is used extensively in process scheduling by the operating system; In this setting the priority may be determined by a combination of factors including how much time has elapsed since the process last ran.

Due to the nature of the priority queue it is most often implemented as a binary heap which gives the following complexities (see Big O notation):

Operation	Complexity	Description
push		puts an element into the queue
pop		takes the highest priority item out of the queue

Java

How to use or build the structure in Java

C++

Priority queues are built into C++, but you must include the correct header

#include <queue>

The following methods are available for queues:

void push(const TYPE&) //adds an element to the priority queue
void pop() //removes element with highest priority
TYPE& top() //returns element with highest priority
int size() //returns number of elements in priority queue
bool empty() //returns true if there are 0 elements

This example puts 5 elements into a priority queue and takes them back out

#include <iostream>
#include <queue>
 
using namespace std;
 
priority_queue<int> q;
int nums[] = {4,1,2,0,3};
 
int main()
{
 
//puts the members of nums on the priority queue
//the size and the element after each push
//the output is
//1 4
//2 1
//3 2
//4 0
//5 3
for(int i=0; i<5; i++) {
    q.push(nums[i]);
    cout << q.size() << " " << nums[i] << endl;
}
 
cout << endl;
 
//removes the element of highest priority until the queue is empty
//the output is "4 3 2 1 0 "
while(!q.empty()) {
    cout << q.top() << " ";
    q.pop();
}
 
cout << endl;
 
return 0;
}

C++ 2

This code explains how to use a custom comparator. It sorts the integers in increasing order instead of decreasing order.

#include <iostream>
#include <queue>
 
using namespace std;
 
class comparator {
    public:
    bool operator()(int& a, int&b){
        return a>b;
    }
};
 
priority_queue<int,vector<int>,comparator> q;
int nums[] = {4,1,2,0,3};
 
int main()
{
 
//puts the members of nums on the priority queue
//the size and the element after each push
//the output is
//1 4
//2 1
//3 2
//4 0
//5 3
for(int i=0; i<5; i++) {
    q.push(nums[i]);
    cout << q.size() << " " << nums[i] << endl;
}
 
cout << endl;
 
//removes the element of highest priority until the queue is empty
//the output is "0 1 2 3 4 "
while(!q.empty()) {
    cout << q.top() << " ";
    q.pop();
}
 
cout << endl;
 
return 0;
}