Priority Queue

In Turkish: Öncelik Kuyruğu
Pronunciation: pry-OR-ih-tee KYOO

Updated September 30, 20263 min read

In short

A priority queue is a collection in which every item has a priority, and the highest-priority item is always removed first, no matter when it was added.

What is a priority queue?

A priority queue is a collection where every item carries a priority, and removing an item always gives you the one with the highest priority rather than the one that arrived first. In a min-priority queue the smallest value counts as the most urgent, and in a max-priority queue the largest does. Its core operations are inserting an item, peeking at the top item, and removing the top item, sometimes called extract-min or extract-max.

A priority queue is an abstract data type, which means it describes behavior, not a particular layout in memory. The standard implementation is a binary heap, which gives O(log n) insert and remove and O(1) peek; a sorted array would make removal cheap but insertion O(n), and an unsorted list the reverse, so the heap is the balanced choice. Many languages ship one, such as Python's heapq module, Java's PriorityQueue, and C++'s std::priority_queue, while JavaScript has none built in, so developers write a small heap or use a library.

An emergency room triage desk is the classic analogy: patients are seen by urgency, so a new arrival with a serious injury goes ahead of someone who has been waiting with a sprained ankle. Priority queues drive operating system and job schedulers, Dijkstra's algorithm and A* search in route planning, simulations that always process the next event in time, merging many sorted files, and keeping the top k results from a huge stream of data. Message brokers and background job systems often offer priority levels built on the same idea.

A priority queue is often confused with a regular queue and with a heap. A queue is strictly first in, first out, while a priority queue ignores arrival order, and items with equal priority come out in no guaranteed order unless you add a sequence number as a tie-breaker. A heap is the data structure most often used to build a priority queue, so the two words are sometimes used interchangeably, but a priority queue can also be built on a balanced tree or other structures.

Key takeaways

A priority queue always removes the highest-priority item first, not the oldest.
It is an abstract data type, most often implemented with a binary heap.
With a heap, insert and remove take O(log n), and peek takes O(1).
Items with equal priority have no guaranteed order unless you add a tie-breaker.
Schedulers, Dijkstra's algorithm, and top-k queries all rely on priority queues.

Example

A job queue that breaks ties by arrival orderpython

import heapq
from itertools import count

queue, arrival = [], count()  # the counter breaks ties between equal priorities
def push(priority, task):
    heapq.heappush(queue, (priority, next(arrival), task))  # O(log n)

push(2, "send newsletter")
push(1, "charge card")
push(2, "resize images")
push(0, "page the on-call engineer")

while queue:
    priority, _, task = heapq.heappop(queue)  # O(log n): lowest number first
    print(priority, task)  # 0 page..., 1 charge..., 2 send..., 2 resize...

Readers ask

What is the difference between a priority queue and a heap?

A priority queue is the abstract behavior: insert items and always remove the most important one. A heap is a concrete data structure that provides that behavior efficiently, which is why most priority queues are built on heaps.

What is the time complexity of a priority queue?

With a binary heap, inserting an item and removing the top item take O(log n), and peeking at the top takes O(1). Building a priority queue from n existing items at once takes O(n).

Does JavaScript have a priority queue?

No, JavaScript has no built-in priority queue. You can write a small binary heap on top of an array or use a library; re-sorting an array after every insert also works for small inputs, but it costs O(n log n) each time.