Module 5 · Interactive topic

Priority Queue

The most urgent item leaves first

A priority queue is like the emergency room: patients are not treated in the order they arrived, the most urgent one goes first. Every item is a value with a priority. Try the two classic ways of keeping the items in an array: sorted (enqueue does the work) and unsorted (dequeue does the work).

  • Enqueueadd a value + its priority
  • Dequeueremove the highest priority
  • Same priorityfirst come, first served
  • Two wayssorted or unsorted array
Priority Queue Ready
size 4 / 8
status OK
leaves next 20 (p1)
  • Best so far
  • Compared
  • New / found
  • Leaving
  • Empty

Ready

Comparisons 0 Shifts 0
Ready

Items are written value:priority (value up to 3 letters or digits, priority 1–9, up to 8 items) · Keyboard: ← → step · Space play / pause · R reset

How it works

Every operation, in plain steps

These are exactly the steps the visualizer animates.

An item is a value with a priority

Every item stores a value and a priority. The items sit in an array, packed from index 0, and n counts them. A rule decides which priority number is served first: the LOWEST number (priority 1 = most urgent) or the HIGHEST. Items with the same priority are served in the order they arrived, first come, first served. Only one small test, better(a, b), knows about the rule.

#define CAPACITY 8

struct Item { int value; int p; };   // p = the priority
struct Item item[CAPACITY];          // the array, packed from index 0
int n = 0;                           // how many items

// better(a, b): does priority a leave before priority b?
int better(int a, int b) { return a < b; }   // lowest number first (use  a > b  for highest first)

Enqueue (sorted array)

  1. Check there is room: n < CAPACITY.
  2. Start at the right end and move left.
  3. Shift every item that leaves before (or with) the new one one place right.
  4. Put the new item in the gap: the array stays sorted.

Dequeue (sorted array)

  1. The item that leaves next is at the right end.
  2. Take item[n − 1].
  3. Make n smaller — nothing has to shift.
  4. So dequeue is O(1).

Enqueue (unsorted array)

  1. Check there is room: n < CAPACITY.
  2. Put the new item at index n.
  3. Make n bigger.
  4. No searching and no shifting: O(1).

Dequeue (unsorted array)

  1. Look at every item, keeping the best one found so far.
  2. On a tie the earlier item stays the best.
  3. Remove it and shift the later items one place left.
  4. Searching and shifting make it O(n).

Equal priorities

  1. Items with the same priority leave in arrival order.
  2. Sorted array: a new item goes to the LEFT of its equals.
  3. Unsorted array: the scan keeps the earlier item.
  4. That is what makes the queue fair.

Peek, Is Empty, Is Full

  1. Peek (sorted array): look at the right end, O(1).
  2. Peek (unsorted array): scan for the best, O(n).
  3. Is Empty: n == 0. Is Full: n == CAPACITY.
  4. None of them changes the queue.

Ascending or descending

  1. Ascending priority queue: the smallest number is served first.
  2. Descending priority queue: the largest number is served first.
  3. Only the better(a, b) test changes.
  4. Everything else works exactly the same.

A faster way: the heap

  1. Each array makes one operation slow: O(n).
  2. A binary heap makes BOTH enqueue and dequeue O(log n).
  3. Schedulers and Dijkstra's algorithm use a heap.
  4. See the Heaps topic.
Algorithm

Pseudocode

Language-independent steps. The visualizer shows the same logic in C, Python and Java.

1 ENQUEUE(x, p) // sorted: the best item is at the right end
2 if n = CAPACITY then overflow
3 i ← n − 1
4 while i ≥ 0 and not better(p, item[i].p)
5 item[i + 1] ← item[i] // shift it right
6 i ← i − 1
7 item[i + 1] ← (x, p)
8 n ← n + 1
Complexity

How fast is each operation?

n = number of items. With an array, one of the two main operations is always O(n): the sorted array pays when it enqueues, the unsorted array pays when it dequeues. A binary heap pays only O(log n) for both.

Operation Best Average Worst Speed
Enqueue (sorted array) O(1) O(n) O(n) Grows with n
Dequeue (sorted array) O(1) O(1) O(1) Instant
Enqueue (unsorted array) O(1) O(1) O(1) Instant
Dequeue (unsorted array) O(n) O(n) O(n) Grows with n
Peek (sorted / unsorted) O(1) / O(n) O(1) / O(n) O(1) / O(n) Grows with n
Enqueue or dequeue (heap) O(log n) O(log n) O(log n) Grows with n

Sorted array versus unsorted array

Sorted array Unsorted array
Enqueue O(n): shifts items to open a gap O(1): adds at the end
Dequeue O(1): takes the right end O(n): scans, then shifts
Peek O(1) O(n)
Where the next item is always at the right end anywhere: it has to be found
Best when you dequeue and peek a lot you enqueue a lot

Queue versus priority queue

Queue Priority queue
Who leaves first? the oldest item the highest priority
An item stores a value a value and a priority
Equal priorities not needed first come, first served
Typical uses printer line, breadth-first search CPU scheduling, emergency room, Dijkstra's algorithm
Practice

Check your understanding

Answer each question — you will see the explanation straight away.

0 / 7 correct
Question 1

Items arrive: A (priority 2), B (priority 1), C (priority 3). With "lowest number first", which is dequeued first?

Question 2

A and B both have priority 2, and A arrived first. Which one leaves first?

Question 3

In a SORTED array priority queue, where is the item that leaves next?

Question 4

How long does enqueue take in an UNSORTED array priority queue?

Question 5

Which operation of an unsorted array priority queue has to look at every item?

Question 6

Which structure makes both enqueue and dequeue O(log n)?

Question 7

In a DESCENDING priority queue, which item is served first?

Assessment

Queues quiz

Test yourself: 5 questions, 70% to pass. Create a free account to take the quiz, save your progress and work towards the certificate.

Create a free account →
← Previous topic Queue Basics Next topic → Double-Ended Queue