# Priority Queue

URL: https://softwaredictionary.org/terms/priority-queue
Category: Data Structures
Last updated: 2026-09-30
In Turkish: Öncelik Kuyruğu
Pronunciation: pry-OR-ih-tee KYOO

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 order

```python
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...
```

## Frequently asked questions

**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.

---

Software Dictionary: https://softwaredictionary.org/ · https://softwaredictionary.org/llms.txt