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

## 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.