Heaps and Heap Implementation of Priority Queues

A priority queue is an abstract data type whose items each carry a priority, and whose remove operation returns an item with the minimum priority currently present, not the item that arrived first.

Programming

Interactive lab

Try it: Stack and Queue

The difference between a stack (last in, first out) and a queue (first in, first out).

How it works

A stack adds (push) and removes (pop) at the same end, the top — the last item added leaves first.
A queue adds (enqueue) at the back and removes (dequeue) from the front — the first item added leaves first.
peek / front look at the next item without removing it.
Adding to a full structure is an overflow; removing from an empty one is an underflow.

Default run (3 steps): Stack (bottom → top): 4, 7. 2 of 8 slots used. Choose an operation. Example: push 9. … Stack is now: 4, 7, 9. Size 3/8.

Simplified: Fixed capacity of 8 items so overflow can be shown; Python lists and collections.deque grow as needed.

Educational simulation

Loading the simulation…

Predicting the Removal Order

Many people hear the phrase priority queue and assume it works like an ordinary line of people waiting: the item added first leaves first. That assumption feels natural, because the word queue suggests a line. This article will test that assumption, then replace it with the rule that a priority queue actually follows.

What do you think happens?

Three items arrive in this order: A with priority 5, then B with priority 1, then C with priority 3. Which item does the first remove operation return if the queue behaves as a priority queue?

A, because it arrived first
B, because it has the minimum priority
C, because it arrived in the middle

Reveal answer

Answer:

B, because it has the minimum priority

A priority queue's remove operation returns an item with the minimum priority currently present, not the item that arrived first. Here B has the smallest priority value, 1, so it leaves first. C (priority 3) would leave next, and A (priority 5) last.

What a Priority Queue Promises

Definition

A priority queue is an abstract data type that represents a collection of items. Each item has an assigned priority, which allows any two items to be compared. Its remove operation returns an item with the minimum priority currently present in the queue.

The key word in that definition is priority. Position in the line is not what decides which item comes out. Notice also what the definition does not promise. It does not promise that items leave in the order they arrived, and it does not promise any particular order for the items still waiting. It promises one thing on each removal: the returned item has the minimum priority among what remains.

The word abstract matters here. The definition describes the behavior a user can rely on, not the internal layout that produces that behavior. A program using a priority queue only needs to know the rule about which item comes out next, not how the items are stored.

Priority Queue Versus a Plain FIFO Queue

A plain first-in, first-out queue removes items in arrival order. A priority queue removes items by priority. The diagram below uses the same three arrivals from the opening prediction. Read the FIFO column first, then the priority queue column, and notice that the same items leave in different orders.

The same three arrivals (A priority 5, B priority 1, C priority 3) leave in arrival order from a FIFO queue, but in minimum-priority order from a priority queue.

In the FIFO column, A leaves first simply because it arrived first. In the priority queue column, B leaves first because it has the smallest priority value, then C, then A. The arrival order did not change, so the difference comes entirely from the removal rule.

Tracing Adds and Removes Step by Step

The best way to see the rule at work is to trace a queue's contents as operations happen. The example below is a generated illustration. Each item is just a number, and the smaller number is treated as the minimum priority. Watch what the queue holds after every step, and check which item each remove returns.

Worked example

Adding three items and removing twice

Start with an empty priority queue. Perform these operations in order: add(7), add(2), add(5), remove(), remove(). For each remove, state which item is returned and what remains.

1
Start
The queue is empty, so isEmpty() would return true at this point.
2
add(7)
The queue now holds {7}. Only one item is present, so it has the minimum priority by default.
3
add(2)
The queue now holds {7, 2}. Both items are present, and the comparison shows 2 is smaller.
4
add(5)
The queue now holds {7, 2, 5}. Adding does not remove anything, and no item leaves the queue.
5
First remove()
Among 7, 2, and 5 the minimum is 2, so remove returns 2. The queue now holds {7, 5}.
6
Second remove()
Among 7 and 5 the minimum is 5, so remove returns 5. The queue now holds {7}.

Result

The removal order is 2, then 5. The item 7 was added first but leaves last, which shows that arrival order does not decide removal.

The Three Essential Operations

The source identifies three operations as essential to a priority queue: add, remove, and isEmpty. The Java PriorityQueue class is written as a parameterized class, PriorityQueue<T>, which implements a priority queue of objects of type T. It also implements the Collection<T> interface, so a priority queue object has every method that interface defines. Only the three operations below are essential to the priority queue concept itself.

1
add: places a new item into the queue. Its job is to make the item available for a later removal according to its priority.
2
remove: removes and returns the item with the minimum priority currently present. This is the operation that embodies the priority rule.
3
isEmpty: reports whether the queue holds no items, so a program can check before calling remove.

Why Items Must Be Comparable

A remove operation that returns the minimum item only makes sense if the queue can decide, for any two items, which one is smaller. The source compares this situation to sorting, because the queue must compare any two items it holds. Without a way to compare items, the phrase minimum priority has no meaning.

Java offers two ways to supply that comparison. The source notes that these mirror the two standard approaches to sorting objects. The first is to have the item's class implement the Comparable interface and its compareTo() method, so the item knows how to compare itself. The second is to supply a Comparator to the PriorityQueue constructor, so the comparison is provided from outside the item.

Two Implementations and Their Costs

The source describes two broad ways to implement a priority queue. The simplest uses a linked list that keeps items in order of increasing priority. In that design, remove is simple, because it removes and returns the first item in the list. Add is the expensive part, because the new item must be inserted into its correct position. The average run time for that add is Theta(n), where n is the number of items in the list.

The source also states that a priority queue can be implemented so that both add and remove have run time Theta(log(n)), which is much more efficient. That efficient version uses a heap. The source does not explain how a heap arranges its items and says it will not discuss that implementation in this section, so this article does not describe the arrangement. What you can rely on is the complexity contrast between the two designs.

Design	Add cost	Remove cost	Note from source
Linked list kept in increasing priority order	Theta(n) on average	Simple: removes the first item	Add is the expensive operation
Heap-based implementation	Theta(log(n))	Theta(log(n))	The efficient version; arrangement not covered in the source

Complexity contrast between the two implementation approaches named in the source

Heap Data Structure Versus the Java Heap

The word heap appears in two different places, and the two uses should not be confused. In this article, a heap is a data structure used to implement a priority queue efficiently. It is a way of organizing the items inside a priority queue so that add and remove run in Theta(log(n)) time.

The Java heap is a different thing. It is the memory region where Java objects are created. A priority queue object lives in that memory like any other object, but the data structure that orders its items is the heap in the first sense. The shared name is the only real connection between the two.

Mistakes Beginners Make with Priority Queues

Common mistake
Assuming a priority queue removes items in arrival order
What it looks like
Adding A, then B, then C, and expecting A to leave first even when A has the largest priority value.
Why it fails
The remove operation returns the item with the minimum priority currently present, not the item that arrived first.
Do this instead
Decide which item leaves by comparing priorities, then check the rule at each removal.
Common mistake
Expecting any particular order for items still waiting
What it looks like
Assuming the queue keeps the remaining items sorted in arrival order after each removal.
Why it fails
The definition promises only that each removal returns a minimum-priority item. It makes no promise about the order of the other items.
Do this instead
Rely only on what remove returns, and do not assume an order for the rest of the queue.
Common mistake
Calling remove without checking whether the queue is empty
What it looks like
Calling remove on a queue that has just become empty.
Why it fails
In Java, remove throws an exception when the queue is empty.
Do this instead
Call isEmpty first, and only call remove when the queue holds at least one item.
Common mistake
Using a priority queue with items that cannot be compared
Why it fails
The queue must decide, for any two items, which has the smaller priority. Without Comparable or a Comparator, that decision cannot be made.
Do this instead
Implement Comparable and compareTo() in the item class, or supply a Comparator to the PriorityQueue constructor.
Common mistake
Confusing the heap data structure with the Java heap

Practice: Predicting Removal Order

EASY

A priority queue starts empty. Perform these operations in order: add(4), add(9), add(1), add(6), remove(), remove(). Using the rule that remove returns the item with the minimum priority currently present, list the two items returned by the removes, in order. Then state how many items remain.

Hints

After each add, list every item currently in the queue before deciding what remove returns.
The first remove looks at 4, 9, 1, and 6. Which of these is smallest?
After the first remove, the second remove looks only at the items still present.

Your attempt (not saved)

Key Takeaways

A priority queue is an abstract data type whose items carry priorities, and its remove operation returns the item with the minimum priority currently present, not the item that arrived first.
The essential operations are add, remove, and isEmpty; in Java, remove throws an exception when the queue is empty, so isEmpty should be checked first.
Items must be comparable, either by implementing Comparable and compareTo(), or by supplying a Comparator to the PriorityQueue constructor.
A linked-list implementation has average add cost Theta(n), while a heap-based implementation can achieve Theta(log(n)) for both add and remove.
The heap that implements a priority queue is a data structure, while the Java heap is the memory region where objects are created; the shared name is the only connection.