Priority Queue
In this page:
What is a Priority Queue?
A priority queue is a data structure where elements come out according to their priority, not according to how long they've been waiting, unlike a regular FIFO queue.
Example: What is a Priority Queue?
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(3); pq.push(10); pq.push(1);
cout << "Highest priority: " << pq.top();
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(3); pq.add(10); pq.add(1);
System.out.println("Highest priority: " + pq.peek());
}
}import heapq
pq = []
for v in (3, 10, 1):
heapq.heappush(pq, -v)
print("Highest priority:", -pq[0])#include <stdio.h>
int main() {
int arr[] = {3, 10, 1};
int maxVal = arr[0];
for (int i = 1; i < 3; i++) if (arr[i] > maxVal) maxVal = arr[i];
printf("Highest priority: %d", maxVal);
return 0;
}Login to try C/C++/Java code in the editor
Insert Priority Elements
Elements are inserted the same way as any other structure, but the priority queue internally reorganizes itself (typically using a heap) so it always knows which element currently has the highest, or lowest, priority.
Example: Insert Priority Elements
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(5); pq.push(20); pq.push(15);
cout << "Top after inserts: " << pq.top();
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(5); pq.add(20); pq.add(15);
System.out.println("Top after inserts: " + pq.peek());
}
}import heapq
pq = []
for v in (5, 20, 15):
heapq.heappush(pq, -v)
print("Top after inserts:", -pq[0])#include <stdio.h>
int main() {
int arr[] = {5, 20, 15};
int maxVal = arr[0];
for (int i = 1; i < 3; i++) if (arr[i] > maxVal) maxVal = arr[i];
printf("Top after inserts: %d", maxVal);
return 0;
}Login to try C/C++/Java code in the editor
Remove by Priority
Removing from a priority queue always returns the current highest-priority element (in a max-priority queue) or lowest-priority element (in a min-priority queue), which is what distinguishes it from a plain queue's strict arrival order.
Example: Remove by Priority
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> pq;
pq.push(5); pq.push(20); pq.push(15);
while (!pq.empty()) { cout << pq.top() << " "; pq.pop(); }
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
pq.add(5); pq.add(20); pq.add(15);
while (!pq.isEmpty()) System.out.print(pq.poll() + " ");
}
}import heapq
pq = []
for v in (5, 20, 15):
heapq.heappush(pq, -v)
while pq:
print(-heapq.heappop(pq), end=" ")#include <stdio.h>
int main() {
int arr[] = {20, 15, 5};
for (int i = 0; i < 3; i++) printf("%d ", arr[i]);
return 0;
}Login to try C/C++/Java code in the editor
Priority Queue Applications
Priority queues are essential to CPU task scheduling (running the most urgent job first), Dijkstra's shortest path algorithm (always expanding the closest unvisited node next), and event-driven simulations that process events in time order.
Example: Priority Queue Applications
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
priority_queue<pair<int, string>> pq;
pq.push({2, "Print doc"}); pq.push({5, "Fix server outage"}); pq.push({1, "Reply email"});
cout << "Next task: " << pq.top().second;
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> b[0] - a[0]);
pq.add(new int[]{2, 0}); pq.add(new int[]{5, 1}); pq.add(new int[]{1, 2});
String[] tasks = {"Print doc", "Fix server outage", "Reply email"};
System.out.println("Next task: " + tasks[pq.peek()[1]]);
}
}import heapq
tasks = [(-2, "Print doc"), (-5, "Fix server outage"), (-1, "Reply email")]
heapq.heapify(tasks)
print("Next task:", tasks[0][1])#include <stdio.h>
int main() {
char *tasks[] = {"Print doc", "Fix server outage", "Reply email"};
int priority[] = {2, 5, 1};
int best = 0;
for (int i = 1; i < 3; i++) if (priority[i] > priority[best]) best = i;
printf("Next task: %s", tasks[best]);
return 0;
}Login to try C/C++/Java code in the editor
Priority Queue Practice
Working through both max-priority and min-priority variants side by side makes the distinction concrete: the underlying operations are identical, only the comparison used to decide priority is flipped.
Example: Priority Queue Practice
#include <iostream>
#include <queue>
using namespace std;
int main() {
priority_queue<int> maxPQ;
priority_queue<int, vector<int>, greater<int>> minPQ;
for (int v : {4, 1, 7}) { maxPQ.push(v); minPQ.push(v); }
cout << "Max: " << maxPQ.top() << ", Min: " << minPQ.top();
return 0;
}import java.util.*;
public class Main {
public static void main(String[] args) {
PriorityQueue<Integer> maxPQ = new PriorityQueue<>(Collections.reverseOrder());
PriorityQueue<Integer> minPQ = new PriorityQueue<>();
for (int v : new int[]{4, 1, 7}) { maxPQ.add(v); minPQ.add(v); }
System.out.println("Max: " + maxPQ.peek() + ", Min: " + minPQ.peek());
}
}import heapq
values = [4, 1, 7]
min_pq = list(values)
heapq.heapify(min_pq)
max_pq = [-v for v in values]
heapq.heapify(max_pq)
print("Max:", -max_pq[0], ", Min:", min_pq[0])#include <stdio.h>
int main() {
int arr[] = {4, 1, 7};
int maxVal = arr[0], minVal = arr[0];
for (int i = 1; i < 3; i++) {
if (arr[i] > maxVal) maxVal = arr[i];
if (arr[i] < minVal) minVal = arr[i];
}
printf("Max: %d, Min: %d", maxVal, minVal);
return 0;
}Login to try C/C++/Java code in the editor
Chapter Quiz — Complete all 5 topics to unlock
0/5 topics done
Complete these topics first: