15.
Priority Queues
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Queues are simply lists that maintain the order of elements using first-in-first-out (FIFO) ordering. A priority queue is another version of a queue in which elements are dequeued in priority order instead of FIFO order.
A priority queue can be either of these two:
- Max-priority, in which the element at the front is always the largest.
- Min-priority, where the element at the front is always the smallest.
You’ll notice the similarity here to the heap data structure that you made in the last chapter. In fact, in this chapter you’ll implement a priority queue using a heap. A priority queue creates a layer of abstraction by focusing on the key operations of a queue and leaving out the additional functionality provided by a heap. This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else. Simplicity for the win!
Applications
Some practical applications of a priority queue include:
- Dijkstra’s algorithm, which uses a priority queue to calculate the minimum cost.
- A* pathfinding algorithm, which uses a priority queue to track the unexplored routes that will produce the path with the shortest length.
- Heapsort, which can be implemented using a priority queue.
- Huffman coding that builds a compression tree. A min-priority queue is used to repeatedly find two nodes with the smallest frequency that do not yet have a parent node.
These are just some of the use cases, but priority queues have many more applications as well.
Common Operations
In Chapter 6, “Queues”, you established the following interface for queues:
abstract interface class Queue<E> {
bool enqueue(E element);
E? dequeue();
bool get isEmpty;
E? get peek;
}
Implementation
You can create a priority queue in the following ways:
Getting Started
Here’s how to use a heap to create a priority queue.
import 'heap.dart';
import 'queue.dart';
// 1
export 'heap.dart' show Priority;
// 2
class PriorityQueue<E extends Comparable<E>> implements Queue<E> {
PriorityQueue({
List<E>? elements,
Priority priority = Priority.max,
}) {
// 3
_heap = Heap<E>(elements: elements, priority: priority);
}
late Heap<E> _heap;
// more to come
}
Implementing the Queue Interface
To implement the Queue interface, add the following to PriorityQueue:
@override
bool get isEmpty => _heap.isEmpty;
@override
E? get peek => _heap.peek;
// 1
@override
bool enqueue(E element) {
_heap.insert(element);
return true;
}
// 2
@override
E? dequeue() => _heap.remove();
Testing it Out
Go to bin/starter.dart and replace the contents of the file with the following code:
import 'package:starter/priority_queue.dart';
void main() {
var priorityQueue = PriorityQueue<num>(
elements: [1, 12, 3, 4, 1, 6, 8, 7],
);
while (!priorityQueue.isEmpty) {
print(priorityQueue.dequeue()!);
}
}
12
8
7
6
4
3
1
1
Challenges
The first challenge below will test your ability to apply the data structure to a practical problem, while the second challenge will give you some more practice implementing a priority queue. As always, you can find the answers in the Challenge Solutions section at the end of the book.
Challenge 1: Prioritize a Waitlist
Your favorite concert was sold out. Fortunately, there’s a waitlist for people who still want to go! However, ticket sales will first prioritize someone with a military background, followed by seniority.
final person = Person(name: 'Josh', age: 21, isMilitary: true);
Challenge 2: List-Based Priority Queue
You’ve learned how to construct a priority queue by implementing the Queue interface with an internal heap data structure. Now your challenge is to do it again, but this time with a List.
Key Points
- A priority queue is often used to retrieve elements in priority order.
- A max-priority queue prioritizes the largest elements, while a min-priority queue, the smallest.
- Wrapping a heap with a queue interface allows you to focus on the key operations of a queue while ignoring unneeded heap operations.