A Priority queue is like a regular queue, except each element has a priority assigned to it. Elements that have a higher priority are dequeued before lower priority elements. Instead of writing my own version of a PriorityQueue
for this book, I'm going to reference an implementation by David Kopec. David's Swift PriorityQueue
is a popular implementation, and he's done a great job of keep it up to date with all of the frequent Swift language changes. You can find the complete code for PriorityQueue
included in this book. I'll also include the GitHub URL to his project at the end of this section.
The PriorityQueue
is a pure Swift implementation of a generic priority queue data structure. It features a straightforward interface and can be used with any type that implements Comparable. It utilizes comparisons between elements rather than numeric priorities to determine order. It uses a classic binary heap implementation with O(log n) complexity for pushes (enqueue) and pops (dequeue...