## Data Structures & Algorithms in Swift

Fourth Edition · iOS 15 · Swift 5.5 · Xcode 13

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 6 chapters

# 24. Priority Queues Written by Vincent Ngo

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

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 }
}
``````

## Implementation

You can create a priority queue in the following ways:

``````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 ...
}
``````
``````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()
}
``````

## Testing

``````var priorityQueue = PriorityQueue(sort: >, elements: [1,12,3,4,1,6,8,7])
while !priorityQueue.isEmpty {
print(priorityQueue.dequeue()!)
}
``````
``````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!
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.