14 Priority Queues¶

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, in which 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 class Queue<E> {
  bool enqueue(E element);
  E? dequeue();
  bool get isEmpty;
  E? get peek;
}

A priority queue has the same operations as a regular queue, so only the implementation will differ:

enqueue: Inserts an element into the queue, and returns true if the operation was successful.
dequeue: Removes the element with the highest priority and returns it. Returns null if the queue was empty.
isEmpty: Checks if the queue is empty.
peek: Returns the element with the highest priority without removing it. Returns null if the queue was empty.

Implementation¶

You can create a priority queue in the following ways:

Sorted list: This is useful to obtain the maximum or minimum value of an element in O(1) time. However, insertion is slow and will require O(n) time since you have to first search for the insertion location and then shift every element after that location.
Balanced binary search tree: This is useful in creating a double-ended priority queue, which features getting both the minimum and maximum value in O(log n) time. Insertion is better than a sorted list, also O(log n).
Heap: This is a natural choice for a priority queue. A heap is more efficient than a sorted list because a heap only needs to be partially sorted. Inserting and removing from a heap are O(log n) while simply querying the highest priority value is O(1).

You’ll implement a priority queue in this chapter using a heap. However, also check out Challenge 2 in which you’ll reimplement a priority queue using a list.

Getting Started¶

Here’s how to use a heap to create a priority queue.

Open up the starter project. In the lib folder, you’ll find the following files:

heap.dart: Contains the heap data structure from the previous chapter.
queue.dart: Contains the interface that defines a queue.

Create a new file in the lib folder called priority_queue.dart and add the following code to it:

import 'heap.dart';
import 'queue.dart';

// 1
export 'heap.dart' show Priority;

// 2
class PriorityQueue<E extends Comparable<dynamic>> 
  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
}

Here are some notes corresponding to the commented numbers:

When you use your priority queue in the future to implement Dijkstra’s algorithm, exporting Priority here will save you from having to import heap.dart separately.
PriorityQueue will conform to the Queue protocol. The generic type E must extend Comparable since you need to sort the elements.
You’ll use this heap to implement the priority queue. By passing an appropriate Priority type into the constructor, PriorityQueue can be used to create either min- or max-priority queues.

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();

The heap data structure makes it easy to implement a priority queue.

You implement enqueue by calling insert on the heap. From the previous chapter, you should recall that when you insert, the heap will sift up to validate itself. The overall complexity of enqueue is O(log n).
By calling dequeue, you remove the root element from the heap by replacing it with the last heap element and then sifting down to validate the heap. The overall complexity of dequeue is also O(log n).

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(
    elements: [1, 12, 3, 4, 1, 6, 8, 7],
  );
  while (!priorityQueue.isEmpty) {
    print(priorityQueue.dequeue()!);
  }
}

Your priority queue has the same interface as a regular queue. Since you didn’t change the default priority, the code above creates a max-priority queue.

Run the code and you’ll see the following numbers are printed to the console in descending order:

That’s all there is to making a priority queue with a heap! Ready to try some challenges?

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.

Use a priority queue to prioritize the order of people on the waitlist. Start by making a Person class that you can instantiate like so:

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.