priority queue

A priority queue is an abstract data type that, like an ordinary queue, dispenses its elements one at a time, but releases the element with the highest priority rather than the one that has waited longest. Each element carries a priority, and retrieval follows that priority instead of insertion order.

Two operations define the structure. Inserting adds an element together with its priority, and removing takes out and returns the element that currently ranks highest. When priorities tie, some implementations preserve insertion order to stay stable, while others leave the outcome unspecified.

A priority queue that serves the smallest key first is a min-priority queue, and one that serves the largest is a max-priority queue. Which form a problem needs depends on whether low or high values represent the most urgent work.

The choice of underlying structure decides how fast those operations run:

  • Binary heap: Keeps elements in a partially ordered tree, giving O(log n) time for both insertion and removal. This is the most common implementation.
  • Sorted array: Keeps elements ordered so removal is constant time, but each insertion costs O(n) to make room.
  • Unsorted array: Inserts in constant time but scans every element, O(n), to find the highest priority on removal.

The interactive heap below builds exactly that partially ordered tree: insert values in any order to watch each one sift up into place, then dequeue to serve the smallest value first while the last leaf sifts back down to repair the heap.

Interactive diagram — enable JavaScript to view.

Priority queues drive Dijkstra’s shortest-path algorithm and A search, Huffman coding, event-driven simulation, and any scheduler that must always pick the most urgent task next. Python provides them through the heapq functions and the thread-safe queue.PriorityQueue class. Both serve the smallest value first, so a plain number priority makes low* values the most urgent. A common trick for max-priority behavior is to insert the negated priority.

Python Stacks, Queues, and Priority Queues in Practice

Tutorial

Python Stacks, Queues, and Priority Queues in Practice

In this tutorial, you'll take a deep dive into the theory and practice of queues in programming. Along the way, you'll get to know the different types of queues, implement them, and then learn about the higher-level queues in Python's standard library. Be prepared to do a lot of coding.

intermediate algorithms data-structures

For additional information on related topics, take a look at the following resources:

By Martin Breuss • Updated Aug. 9, 2026
Computer Science Glossary Share Feedback