Data Structureseasy

What is a priority queue?

Answer

A priority queue removes the element with the highest (or lowest) priority first, not the oldest. It’s commonly implemented with a heap, so insert/remove is O(log n).

import java.util.PriorityQueue;

PriorityQueue<Integer> pq = new PriorityQueue<>();
pq.add(5);
pq.add(1);
System.out.println(pq.poll()); // 1

Advanced answer

Deep dive

A priority queue is an ADT where removal returns the element with the best priority (min or max). The most common implementation is a binary heap.

Typical costs for a binary heap:

peek (min/max): O(1)
insert: O(log n)
pop (remove min/max): O(log n)

It shines when you repeatedly need the next best item while the collection changes over time.

Typical uses

Dijkstra / A*: always expand the smallest tentative distance.
Scheduling: run the most urgent job first.
Top-K: keep a min-heap of size k while scanning a stream.

Examples

// Min-heap by first field (priority)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
pq.add(new int[]{5, 42});
pq.add(new int[]{1, 7});
int[] next = pq.poll(); // [1, 7]

Common pitfalls

Assuming stable ordering for equal priorities (not guaranteed).
Expecting fast removal of arbitrary elements (a heap needs extra indexing for that).