What is a priority queue? A simple guide with a game

If you have seen the phrase in a coding course and wondered what is a priority queue?, the short answer is this: it is a collection where the next item out is always the most important one, not the oldest one. You put items in with a priority, and you take them out in priority order. This guide explains how that works, how it is built, and where you will meet it, including inside a browser game you can play.

What is a priority queue?

A priority queue is an abstract data type. That means it is defined by what it does, not by how it is stored. It holds items, each with a priority, and it promises one thing: when you ask for the next item, you get the one with the best priority.

"Best" depends on your choice. In a min priority queue, the smallest number wins. In a max priority queue, the largest number wins. Most languages ship a min version or let you flip the comparison.

Think of an emergency room. Patients do not see the doctor in the order they arrived. A patient with a serious injury goes first. That is a priority queue.

How a priority queue differs from a regular queue

A regular queue is first in, first out. The item that has waited longest leaves first. A stack is the opposite: last in, first out.

A priority queue ignores arrival order. Add these tasks in this order:

• write report with priority 3
• fix crash with priority 1
• reply to email with priority 2

A regular queue returns them in the same order. A min priority queue returns fix crash, then reply to email, then write report. The insertion order does not matter at all.

One detail to watch: when two items share a priority, many implementations do not promise which comes first. If order among equals matters, add a counter as a tie breaker.

Core operations: insert, peek, and extract

Almost every priority queue offers the same three operations. The names vary by language.

• Insert (also push or enqueue): add an item with its priority.
• Peek (also top or find min): look at the best item without removing it.
• Extract (also pop or dequeue): remove and return the best item.

How priority queues work under the hood: binary heaps

You could store items in a sorted list. Peek would be instant, but every insert would have to shift items to keep the list in order. You could also use an unsorted list. Insert would be instant, but every extract would scan everything to find the best item.

A binary heap is the usual middle path. It is a binary tree with one rule: every parent is better than or equal to its children. In a min heap, the smallest value sits at the top. The rest is only loosely ordered, and that looseness is what makes it cheap.

A heap is usually stored in a plain array with no pointers. For the item at index i, its children sit at 2i + 1 and 2i + 2, and its parent sits at (i - 1) / 2, rounded down.

Two small repair moves keep the rule true:

1. Insert: put the new item at the end of the array. While it is better than its parent, swap them. This is called sifting up.
2. Extract: take the top item. Move the last item into the top slot. While it is worse than a child, swap it with the better child. This is called sifting down.

Each repair walks one path through the tree, never the whole thing. A tree of a million items is only about twenty levels deep, so a repair takes about twenty swaps at most.

Time complexity of priority queue operations

With n items in a binary heap:

• Peek takes constant time, because the best item is always at index 0.
• Insert takes logarithmic time, written O(log n), because sifting up walks one path.
• Extract takes O(log n) for the same reason.
• Building a heap from n items you already have takes O(n) with the standard method, which is faster than inserting them one at a time.

Compare that with the sorted list, where insert costs O(n), and the unsorted list, where extract costs O(n). The heap keeps both operations cheap. That is why it is the default choice.

A simple priority queue example

Here is the idea in plain steps, so it works in any language. Say you are building a to do app that always shows the most urgent task.

1. Create an empty min priority queue.
2. Call insert("write report", 3), then insert("fix crash", 1), then insert("reply to email", 2).
3. Call peek(). It returns fix crash and leaves it in the queue.
4. Call extract(). It returns fix crash and removes it.
5. Call extract() again. It returns reply to email.
6. Call insert("deploy hotfix", 0). Now the next extract() returns deploy hotfix, even though it arrived last.

Step 6 is the whole point. New, urgent work can jump ahead at any time, and you never re-sort anything yourself.

In Python, the standard heapq module gives you this with heappush and heappop. In Java, it is PriorityQueue. In C#, there is a PriorityQueue type, and a sorted set also works. In JavaScript you usually write a small heap yourself or use a library.

Real-world uses: Dijkstra, schedulers, and game AI

Priority queues show up wherever "do the most important thing next" is the rule.

• Operating system schedulers pick which task runs next based on priority.
• Event simulations keep upcoming events ordered by time and always handle the earliest one.
• Merging sorted lists works by keeping the front item of each list in a queue.
• Shortest path search uses one to decide which place to explore next.

The last one is the famous case. Dijkstra's algorithm finds the cheapest route through a graph when steps have different costs. It is a cousin of breadth-first search. Breadth-first search uses a plain queue and works when every step costs the same. Swap the plain queue for a priority queue ordered by total cost so far, and you get Dijkstra.

A worked example inside a tank game

Tank City Zero Day, the second game on Tank City Reboot, uses exactly this to steer its enemies. The code builds a grid of 25 by 25 cells and runs Dijkstra's algorithm over it, with a sorted set acting as the priority queue. A step costs 1, and a step onto firewall costs 4, because the firewall has to be shot through first.

Cells holding silicon, coolant, or the core cannot be stood on, so they are skipped. Steps go in eight directions, and a diagonal step is skipped when either of the two cells it cuts across is blocked.

Here is what that cost rule means in practice. Suppose a worm is five steps from the core in a straight line, and one of those cells is firewall. Four open steps plus one firewall step cost 4 + 4 = 8. A detour around the wall through seven open cells costs 7. The queue always expands the cheapest cell first, so the detour wins and the worm walks around. Make the detour cost 9 instead, and the straight route wins, so the worm shoots through the wall. These numbers are an illustration of mine, but the rule behind them is the one in the code.

There is a second smart choice. The search runs from the goal outward, so one run fills every cell with its distance to the goal. After that, each enemy only has to step to the neighboring cell with the lowest distance. No enemy runs its own search.

The game builds two such maps. Botnet drones walk the map whose goal is your tank, and it is rebuilt about every 0.3 seconds as you move. Worms and ransomware walk the map whose goal is the cells next to the core, and it is rebuilt when the walls change, at most every 0.2 seconds. When a walker is stuck behind firewall, it keeps shooting the wall. If it stays stuck for about 1.4 seconds and no firewall is in the way, it steps to a random neighbor.

That is a priority queue doing real work, 0.3 seconds at a time. When you play, the enemies do not wander, they take the cheapest road. Zero Day's own page is at tankcityreboot.vlvd.net/zero-day.

Frequently asked questions

Is a priority queue the same as a heap?

No. A priority queue is the behavior: the best item comes out first. A heap is one common way to build it, but a sorted set or balanced tree can do the job too.

What is the time complexity of a priority queue?

With a binary heap, peek is O(1), and insert and extract are O(log n). Building a heap from existing items takes O(n).

What happens when two items have the same priority?

Most implementations do not promise an order between them. If you need first come, first served among equals, store an increasing counter with each item and use it as a tie breaker.

When should I use a priority queue instead of sorting a list?

Use a priority queue when items keep arriving and you only need the best one each time. Sorting everything again after every insert wastes work, while a heap repairs itself in O(log n).

Get started

The best way to learn a data structure is to meet it doing something. Zero Day is one click away. Play a few waves of Zero Day, watch how the worms choose between a wall and a detour, then try writing a small priority queue of your own and give it a handful of weighted steps.

Play Tank City Reboot: it is free, plays in your browser on a computer or a phone, and needs no account.