24. Priority Queues

Written by Vincent Ngo

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 using FIFO ordering. For example, a priority queue can either be:

1. Max-priority, in which the element at the front is always the largest.
2. Min-priority, in which the element at the front is always the smallest.

A priority queue is especially useful when identifying the maximum or minimum value given a list of elements. In this chapter, you will learn the benefits of a priority queue and build one by leveraging the existing queue and heap data structures that you studied in previous chapters.

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.
• Heap sort, 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 8, Queues, you established the following protocol for queues:

public protocol Queue {
  associatedtype Element
  mutating func enqueue(_ element: Element) -> Bool
  mutating func dequeue() -> Element?
  var isEmpty: Bool { get }
  var peek: Element? { get }
}

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

The priority queue will conform to the Queue protocol and implement the common operations:

• enqueue: Inserts an element into the queue. Returns true if the operation was successful.

• dequeue: Removes the element with the highest priority and returns it. Returns nil if the queue was empty.

• isEmpty: Checks if the queue is empty.

• peek: Returns the element with the highest priority without removing it. Returns nil if the queue was empty.

Let’s look at different ways to implement a priority queue.

Implementation

You can create a priority queue in the following ways:

1. Sorted array: 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) since you have to insert it in order.
2. 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 array, also in O(log n).
3. Heap: This is a natural choice for a priority queue. A heap is more efficient than a sorted array because a heap only needs to be partially sorted. All heap operations are O(log n) except extracting the min value from a min priority heap is a lightning-fast O(1). Likewise, extracting the max value from a max priority heap is also O(1).

Next, you will look at how to use a heap to create a priority queue. Open up the starter playground to get started. In the Sources folder, you will notice the following files:

1. Heap.swift: The heap data structure (from the previous chapter) you will use to implement the priority queue.
2. Queue.swift: Contains the protocol that defines a queue.

In the main playground page, add the following:

struct PriorityQueue<Element: Equatable>: Queue { // 1

  private var heap: Heap<Element> // 2

  init(sort: @escaping (Element, Element) -> Bool,
       elements: [Element] = []) { // 3
    heap = Heap(sort: sort, elements: elements)
  }

  // more to come ...
}

Let’s go over this code:

1. PriorityQueue will conform to the Queue protocol. The generic parameter Element must conform to Equatable as you need to compare elements.
2. You will use this heap to implement the priority queue.
3. By passing an appropriate function into this initializer, PriorityQueue can be used to create both min and max priority queues.

To conform to the Queue protocol, add the following right after the init(sort:elements:) initializer:

var isEmpty: Bool {
  heap.isEmpty
}

var peek: Element? {
  heap.peek()
}

mutating func enqueue(_ element: Element) -> Bool { // 1
  heap.insert(element)
  return true
}

mutating func dequeue() -> Element? { // 2
  heap.remove()
}

The heap is a perfect candidate for a priority queue. You need to call various methods of a heap to implement the operations of a priority queue!

1. From the previous chapter, you should understand that, by calling enqueue(_:), you insert into the heap, and the heap will sift up to validate itself. The overall complexity of enqueue(_:) is O(log n).
2. By calling dequeue(_:), you remove the root element from the heap by replacing it with the last element in the heap and then sift down to validate the heap. The overall complexity of dequeue() is O(log n) .

Testing

Add the following to your playground:

var priorityQueue = PriorityQueue(sort: >, elements: [1,12,3,4,1,6,8,7])
while !priorityQueue.isEmpty {
  print(priorityQueue.dequeue()!)
}

You’ll notice that a priority queue has the same interface as a regular queue. The previous code creates a max priority queue. Notice that the elements are removed from largest to smallest. The following numbers are printed to the console:

12
8
7
6
4
3
1
1

Key points

• A priority queue is often used to find the element in priority order.
• It creates a layer of abstraction by focusing on key operations of a queue and leaving out additional functionality provided by the heap data structure.
• This makes the priority queue’s intent clear and concise. Its only job is to enqueue and dequeue elements, nothing else!
• Composition for the win!