A Generic Priority Queue in Pure Swift

David Kopec

Last update: Dec 22, 2022

Related tags

Data Structures / Algorithms swift data-structure astar-algorithm priority-queue priorityqueue min-heap max-heap priority-queues

Overview

SwiftPriorityQueue

SwiftPriorityQueue is a pure Swift (no Cocoa) implementation of a generic priority queue data structure, appropriate for use on all platforms (macOS, iOS, Linux, etc.) where Swift is supported. It features a straightforward interface and can be used with any type that implements Comparable. It utilizes comparisons between elements rather than separate numeric priorities to determine order.

Internally, SwiftPriorityQueue uses a classic binary heap, resulting in O(lg n) pushes and pops. It includes in-source documentation, an A* based example maze solving program (for macOS), and unit tests (pull requests are welcome for additional unit tests in particular).

Features

Easy-to-use method interface
Small, self contained, pure Swift code base
Classic binary heap implementation with O(lg n) pushes and pops
Iterable through standard Swift for...in loops (implements Sequence and IteratorProtocol)
In-source documentation
A fun maze solving A* based example program

Installation

Release 1.3.0 and above supports Swift 5. Use release 1.2.1 for Swift 4. Use release 1.1.2 for Swift 3 and Swift 2 support. Use release 1.0 for Swift 1.2 support.

CocoaPods

Use the CocoaPod SwiftPriorityQueue.

Swift Package Manager (SPM)

Add this repository as a dependency.

Manual

Copy SwiftPriorityQueue.swift into your project.

Documentation

There is a large amount of documentation in the source code using the standard Swift documentation technique (compatible with Jazzy). Essentially though, SwiftPriorityQueue has the three critical methods you'd expect - push(), pop(), and peek().

Initialization

When you create a new PriorityQueue you can optionally specify whether the priority queue is ascending or descending. What does this mean? If the priority queue is ascending, its smallest values (as determined by their implementation of Comparable aka <) will be popped first, and if it's descending, its largest values will be popped first.

var pq: PriorityQueue<String> = PriorityQueue<String>(ascending: true)

You can also provide an array of starting values to be pushed sequentially immediately into the priority queue.

var pq: PriorityQueue<Int> = PriorityQueue<Int>(startingValues: [6, 2, 3, 235, 4, 500])

Or you can specify both.

var pq: PriorityQueue<Int> = PriorityQueue<Int>(ascending: false, startingValues: [6, 2, 3, 235, 4, 500])

Or you can specify neither. By default a PriorityQueue is descending and empty. As you've probably noticed, a PriorityQueue takes a generic type. This type must be Comparable, as its comparison will be used for determining priority. This means that your custom types must implement Comparable and utilize the overridden < to determine priority.

Methods

PriorityQueue has all of the standard methods you'd expect a priority queue data structure to have.

push(element: T) - Puts an element into the priority queue. O(lg n)
pop() -> T? - Returns and removes the element with the highest (or lowest if ascending) priority or nil if the priority queue is empty. O(lg n)
peek() -> T? - Returns the element with the highest (or lowest if ascending) priority or nil if the priority queue is empty. O(1)
clear() - Removes all elements from the priority queue.
remove(item: T) - Removes the first found instance of item in the priority queue. Silently returns if not found. O(n)
removeAll(item: T) - Removes all instances of item in the priority queue through repeated calls to remove(). Silently returns if not found.

Properties

count: Int - The number of elements in the priority queue.
isEmpty: Bool - true if the priority queue has zero elements, and false otherwise.

Standard Swift Protocols

PriorityQueue implements IteratorProtocol, Sequence and Collection so you can treat PriorityQueue like any other Swift sequence/collection. This means you can use Swift standard library fucntions on a PriorityQueue and iterate through a PriorityQueue like this:

for item in pq {  // pq is a PriorityQueue<String>
    print(item)
}

When you do this, every item from the PriorityQueue is popped in order. PriorityQueue also implements CustomStringConvertible and CustomDebugStringConvertible.

print(pq)

Note: PriorityQueue is not thread-safe (do not manipulate it from multiple threads at once).

Just for Fun - A* (`astar.swift`)

A* is a pathfinding algorithm that uses a priority queue. The sample program that comes with SwiftPriorityQueue is a maze solver that uses A*. You can find some in-source documentation if you want to reuse this algorithm inside astar.swift.

Authorship & License

SwiftPriorityQueue is written by David Kopec and released under the MIT License (see LICENSE). You can find my email address on my GitHub profile page. I encourage you to submit pull requests and open issues here on GitHub.

Comments

Set watchOS deployment target to 2.0

I just added a single line to the .podspec file to support watchOS platform. I'm not sure if this is enough for the support, can you kindly check and accept my pull request if so.

opened by halileohalilei 8
Performance improvement (addresses #15)

This update implements some lower-level functions to improve the performance of standard heap operations on SwiftPriorityQueue and adds performance tests for init, pop, push and remove. Hopefully the improvement is sufficient to close #15.

A naive implementation replacing sink and swim with versions that can be called from inside Array.withUnsafeMutableBufferPointer(_:) already gave promising performance for init, pop and push. (See forked master branch. This might represent a good compromise solution if the final code is deemed to be too complex.)

A more in-depth rewrite of the internal code (with inspiration from libcxx/include/algorithm) gave further performance improvements, although the resulting code is less "easy" to understand. In an effort to aid readability, the new code is extensively (some might say excessively!) marked up.

Building a SwiftPriorityQueue from an Array of 100,000 values went from 17.8 ms to 4.1 ms. Emptying a SwiftPriorityQueue with 100,000 values using pop() went from 2.11 s to 0.36 s. Calling remove(_:) on 100 random items from a SwiftPriorityQueue with 100,000 values went from 2.36 s to 0.277 s.

Building a SwiftPriorityQueue by calling push(_:) 100,000 times went from 118 ms to 149 ms. Not certain what happened there! Further investigation may be required, but in any case, the performance improvement in pop() more than compensates in normal usage where pop() and push(_:) are called equally often.

opened by peteraisher 2
Pop performance (addresses #15)

I've managed to get a decent speed-up for pop() without an extensive rewrite.

Profiling testPopPerformance() shows that ~ 70% of the execution time for pop() is taken up by MutableCollection.swapAt(_:_:) and another ~ 13% is Array.subscript.getter.

Implementing the swap and the sink inside a call to Array.withUnsafeMutableBufferPointer(_:) gives a speedup of around 9x (on the release build) on my machine and puts the performance of pop() on a level with push(_:) and remove(_:).

I think the performance gap must be a case of the compiler just not figuring out the optimization for pop(), since all of the other public functions which call sink(_:) and swim(_:) are plenty fast.

opened by peteraisher 1
Fix performance tests
Change code like

var pq = … measure { [mutate pq] }

into code like

let original = … measure { var pq = original [mutate pq] }

Since the measure block executes multiple times, the variable is otherwise different on successive calls.

(The change looks more than it is since the indentation is also fixed!)
opened by peteraisher 1
Can we improve on the performance of pop()?

I came across this article in which the performance of SwiftPriorityQueue was far lower than both an Objective-C priority queue and the C++ STL priority queue because we're spending 68% of his tests in pop() whereas they are spending <10% of their time in his tests on pop(). What can be improved about our pop() implementation? Here's the article, and the relevant section is 6.2: https://miun.diva-portal.org/smash/get/diva2:1135549/FULLTEXT01.pdf

opened by davecom 1

crashes if the element which is the last in the heap gets removed

For silly reasons I unfortunately can't contribute code to most open-source projects. But here's a test case that crashes 100% for me:

    func testRemoveLastInHeap() {
        var pq: PriorityQueue<Int> = PriorityQueue<Int>()
        pq.push(1)
        pq.push(2)
        
        pq.remove(1)
        
        let expected: [Int] = [2]
        var actual: [Int] = []
        for j in pq {
            actual.append(j)
        }
        
        XCTAssertEqual(expected, actual)
    }

with

Exception Type:        EXC_BAD_INSTRUCTION (SIGILL)
Exception Codes:       0x0000000000000001, 0x0000000000000000
Exception Note:        EXC_CORPSE_NOTIFY

Termination Signal:    Illegal instruction: 4
Termination Reason:    Namespace SIGNAL, Code 0x4
Terminating Process:   exc handler [0]

Application Specific Information:
fatal error: Index out of range
 

Thread 0 Crashed:: Dispatch queue: com.apple.main-thread
0   libswiftCore.dylib            	0x000000010bf41de0 specialized _fatalErrorMessage(_:_:file:line:flags:) + 96
1   libswiftCore.dylib            	0x000000010bd6e1b5 _ArrayBuffer._checkInoutAndNativeTypeCheckedBounds(_:wasNativeTypeChecked:) + 261
2   libswiftCore.dylib            	0x000000010bd86067 Array.subscript.getter + 103
3   com.oaksnow.SwiftPriorityQueueTests	0x000000010cebc68c PriorityQueue.swim(_:) + 348 (SwiftPriorityQueue.swift:144)
4   com.oaksnow.SwiftPriorityQueueTests	0x000000010cebcdb1 PriorityQueue.remove(_:) + 657 (SwiftPriorityQueue.swift:97)
5   com.oaksnow.SwiftPriorityQueueTests	0x000000010ceba858 SwiftPriorityQueueTests.testRemoveLastInHeap() + 216 (SwiftPriorityQueueTests.swift:116)
6   com.oaksnow.SwiftPriorityQueueTests	0x000000010cebad04 @objc SwiftPriorityQueueTests.testRemoveLastInHeap() + 36

The problem is that swim(index) will access heap[index] but if in

    public mutating func remove(_ item: T) {
        if let index = heap.index(of: item) {
            heap.swapAt(index, heap.count - 1)
            heap.removeLast()
            swim(index)
            sink(index)
        }
    }

index turns out to be the last element (which gets removed in heap.removeLast()), then swim(index) will lead to a array OOB crash.

As I said I can't contribute the code to fix it but the only thing that's needed is not to call swapAt, swim or sink in the case index is the last element in heap.

opened by weissi 1

Quick question

As a data structure that might need to support a huge amount of popping, why is the priority queue a struct? I'm asking since--to my knowledge--the mutating functions will create a new priority queue every time they're called. Or is it optimized away?

opened by anohren 1

tests not SwiftPM compatible

when I try to run the tests with SwiftPM I get:

$ swift test
Compile Swift Module 'SwiftPriorityQueue' (1 sources)
error: no tests found; create a target in the 'Tests' directory

opened by weissi 0

Get rid of Collection conformance or implement it differently

Added test showing that Collection conformance doesn't match the Sequ…ence conformance: when iterating elements via iterator the PriorityQueue uses the pop() method, effectively returning the elements in order. On the other hand if one iterates via indexes subscription, the elements are returned in the same order as they are stored in the underlaying storage, which doesn't necessarily matches the order in which elements are popped via the pop() method.

Fix: get rid of Collection conformance, otherwise implement a different Index type which takes into account how the effective order elements are popped out from the storage (most likely subscripting or creation of indexes won't be an O(1) operation).

opened by vale-cocoa 4