bouke / swift-priorityqueue

Binary heap implementation in Swift

Swift-PriorityQueue

When included as a framework, import it as any other framework:

import PriorityQueue

The priority queue is defined as a generic and initialized with a comparison callback, like PriorityQueue<T>((T, T) -> Bool). For example, it can operate on characters like this:

var characters = PriorityQueue<Character>(<)
characters.push("C")
characters.push("B")
characters.push("A")

println("Characters:")
for p in characters {
    println(" * \(p)")
}
println()

This would print:

 * A
 * B
 * C

A more real-world use-case would operate on structs or classes, like this:

struct Node {
    let priority: Int
}

var nodes = PriorityQueue<Node>({ $0.priority < $1.priority })
nodes.push(Node(priority: 4))
nodes.push(Node(priority: 5))
nodes.push(Node(priority: 3))
nodes.push(Node(priority: 1))

println("Nodes:")
for node in nodes {
    println(" * Node(priority: \(node.priority))")
}
println()

This would print:

Nodes:
* Node(priority: 1)
* Node(priority: 3)
* Node(priority: 4)
* Node(priority: 5)

Removing items

var ints = PriorityQueue<Int>(<)
ints.push(3)
ints.remove(3)  // Returns 3
ints.remove(3)  // Returns nil

Inspecting the heap

ints.push(5)
ints.push(4)
ints.heap  // Returns [4, 5]

Alternatives

• CFBinaryHeap (once CFunctionPointer becomes available)
• Swift-DataStructures/MinPQ
• davecom/SwiftPriorityQueue

Development

Playground

Rebuild this playground with the following command:

rm -rf README.playground/
playground README.md --platform ios

Credits

This library was written by Bouke Haarsma.

swift-priorityqueue's Issues

Generator should not mutate the PriorityQueue

extension PriorityQueue: GeneratorType { public typealias Element = T public func next() -> Element? { return pop() } }

Just iterating the elements causes the PriorityQueue to be cleared out.
If you use any of the swift functions that iterate over SequenceType, functions like contains() the queue also gets cleared.