PriorityQueue API Review
Hey everyone! After several rounds of feedback, we have the PR for adding a priority queue to the repo in a pretty good spot.
@kylemacomber recommended we post an overview of the API here for review. Please take a look at the APIs presented below (as well as the associated code, if interested) and provide any feedback.
- Do the type, function, and parameter names make sense?
- Does the performance match your expectations?
- Does the
Sequenceconformance (i.e. exposing two separate iterators) make sense? - Any other feedback?
Thanks!
- Authors: Tyler Stromberg, Amanuel Ephrem, Joakim Hassila, and Tim Vermeulen
- Implementation: PR #51
Introduction
Priority queues are useful data structures that can be leveraged across a variety of applications (sorting algorithms, graph algorithms, network clients, task managers, etc).
One common way to implement a priority queue is with an array-backed binary heap. This provides performant lookups (O(1)) of the lowest or highest priority element (depending on whether it's a min-heap or max-heap) as well as insertion and removal (O(log n)).
A variant on this, the min-max heap, allows for performant lookups and removal of both the lowest and highest priority elements by interleaving min and max levels in the backing array (see details below).
This proposal adds an implementation of a double-ended priority queue built on a min-max heap.
Design
/// A double-ended priority queue built on top of a [Min-Max Heap](https://en.wikipedia.org/wiki/Min-max_heap)
/// data structure.
///
/// In a min-max heap, each node at an even level in the tree is less than all
/// its descendants, while each node at an odd level in the tree is greater than
/// all of its descendants.
///
/// The implementation is based off [this paper](http://akira.ruc.dk/~keld/teaching/algoritmedesign_f03/Artikler/02/Atkinson86.pdf).
public struct PriorityQueue<Element: Comparable>
We originally started with the PriorityQueue type wrapping a MinMaxHeap. Ultimately, the former ended up being really thin and didn't seem to add much value, so the two layers were merged.
Min-max heap
"A min-max heap is a complete binary tree data structure." This means that all the levels in the tree are filled except the last and that they are filled from left to right. The tree can be stored in an array:
// Min-max heap:
8
71 41
31 10 11 16
46 51 31 21 13
// Array representation:
[8, 71, 41, 31, 10, 11, 16, 46, 51, 31, 21, 13]
Heap property: Each element in an even level in the tree is less than all its descendants; each element in an odd level in the tree is greater than all its descendants. Mutations to the heap must maintain this heap property.
The levels start at 0 (even), so the smallest element in the tree is at the root. In the example above, the root of the tree is 8, which is the smallest element. The next level in the tree (containing 71 and 41) is a max level, so those elements are greater than all their respective descendants. Because this is the first max level in the tree, the largest element in the tree is one of the two elements.
Note that the comparisons only take into account descendants — it is possible, for example, for elements at a lower level to be larger than elements in a different branch that are higher up the tree. In the example above, 41 isn't the second-largest element in the tree, but it is the largest element in the right branch of the root node.
Initialization
There are a couple of options for initializing a priority queue. The first is an empty queue:
/// Creates an empty queue.
public init()
You can also create a queue from an existing sequence in linear time:
/// Initializes a queue from a sequence.
///
/// Utilizes [Floyd's linear-time heap construction algorithm](https://en.wikipedia.org/wiki/Heapsort#Floyd's_heap_construction).
///
/// - Complexity: O(n), where `n` is the length of `elements`.
public init<S: Sequence>(_ elements: S) where S.Element == Element
Insertion
Of a single element
To insert an element into a queue, call insert(_:):
/// Inserts the given element into the queue.
///
/// - Complexity: O(log `count`) / 2
public mutating func insert(_ element: Element)
This works by adding the new element into the end of the backing array and then bubbling it up to where it belongs in the heap.
Of a sequence of elements
You can also insert a sequence of elements into the queue:
/// Inserts the elements in the given sequence into the priority queue.
///
/// - Parameter newElements: The new elements to insert into the queue.
///
/// - Complexity: O(n * log `count`), where `n` is the length of `newElements`.
public mutating func insert<S: Sequence>(contentsOf newElements: S) where S.Element == Element
This is currently a naĂŻve implementation where we simply iterate over the elements and call insert(_:) with each one.
Future work: Figure out a more performant way of doing this.
Lookup
As mentioned earlier, the lowest and highest priority elements can be queried in constant time:
/// Returns the element with the lowest priority, if available.
///
/// - Complexity: O(1)
public func min() -> Element?
/// Returns the element with the highest priority, if available.
///
/// - Complexity: O(1)
public func max() -> Element?
In a min-max heap, the smallest element is stored at index 0; the largest element is stored at either index 1 or index 2, the first max level in the heap (so to look up the largest, we compare the two and return the larger one).
We also expose a read-only view into the array-backed min-max heap, should somebody need that.
/// A read-only view into the underlying heap.
///
/// In the current implementation, the elements aren't _arbitrarily_ ordered,
/// as a min-max heap is used for storage. However, no guarantees are given as
/// to the ordering of the elements.
///
/// - Complexity: O(1)
public var unordered: [Element]
Removal
Removal has logarithmic complexity, and removing both the lowest and highest priority elements is supported:
/// Removes and returns the element with the lowest priority, if available.
///
/// - Complexity: O(log `count`)
public mutating func popMin() -> Element?
/// Removes and returns the element with the highest priority, if available.
///
/// - Complexity: O(log `count`)
public mutating func popMax() -> Element? {
To remove the lowest priority element, we remove and return the element at index 0. The element at the end of the backing array is put in its place at index 0, and then we trickle it down to where it belongs in the heap. To remove the highest priority element, we do the same except the index is whatever the index of the highest priority element is (see above) instead of 0.
We also have non-optional flavors that assume the queue isn't empty:
/// Removes and returns the element with the lowest priority.
///
/// The queue *must not* be empty.
///
/// - Complexity: O(log `count`)
public mutating func removeMin() -> Element
/// Removes and returns the element with the highest priority.
///
/// The queue *must not* be empty.
///
/// - Complexity: O(log `count`)
public mutating func removeMax() -> Element
Iteration
PriorityQueue itself doesn't conform to Sequence, because of the potential confusion around which direction it should iterate (highest-to-lowest priority? lowest-to-highest?). Instead, we expose two iterators that conform to Sequence:
/// Returns an iterator that orders elements from lowest to highest priority
public var ascending: Iterator
/// Returns an iterator that orders elements from highest to lowest priority
public var descending: Iterator
Example usage
Let's pretend we have some tasks that we need to process and each has a priority. We want to process the highest-priority tasks first.
struct Task: Comparable {
let description: String
let priority: Float // Between 0.0 and 1.0
let work: () -> Void
static func < (lhs: Task, rhs: Task) -> Bool {
lhs.priority < rhs.priority
}
}
// Create our queue
var queue = PriorityQueue<Task>()
// Add some Tasks
let cleanupTask = Task(description: "Background cleanup", priority: 0.1) {
// ...
}
queue.insert(cleanupTask)
let uploadTask = Task(description: "Submit payment", priority: 1) {
// ...
}
queue.insert(uploadTask)
let generateThumbnails = Task(description: "Generate thumbnails", priority: 0.5) {
// ...
}
queue.insert(generateThumbnails)
// Now let's perform all our work
for task in queue.descending {
print("Starting '\(task.description)'")
task.work()
}
// This will print out:
// Starting 'Submit payment'
// Starting 'Generate thumbnails'
// Starting 'Background cleanup'
// The iteration above can also be done via a while loop:
while let task = queue.popMax() {
print("Starting '\(task.description)'")
task.work()
}
Source impact
This is purely additive. No existing APIs were changed, deprecated, or removed.
Potential future directions
- Add support for merging two
PriorityQueues - Add
replaceMinandreplaceMaxfunctions - Implement a more performant algorithm for
insert(contentsOf:)
Split priority out of the Element type
Sometimes, it doesn't make sense for a type to conform to Comparable directly, but it may have a property that does — e.g. Task.priority. Making PriorityQueue generic around both the element to be stored and its priority allows more flexibility.
This could potentially be done via a KeyPath or by separating priority from the Element type altogether (see discussion in the linked issue).
