GenericPriorityQueue

public struct GenericPriorityQueue<
  Priority: Comparable,
  Payload,
  Heap: RandomAccessCollection & RangeReplaceableCollection & MutableCollection,
  ElementLocations: PriorityQueueIndexer
>: Queue where
  Heap.Element == PriorityQueueElement<Priority, Payload>,
  ElementLocations.Key == Payload,
  ElementLocations.Value == Heap.Index
extension GenericPriorityQueue: RandomAccessCollection
extension GenericPriorityQueue: CustomStringConvertible
extension GenericPriorityQueue: DefaultInitializable
where
  Heap: DefaultInitializable,
  ElementLocations: DefaultInitializable

A collection of Prioritys and Payloads that allows for efficient retrieval of the smallest priority and its associated payload, and insertion of payloads at arbitrary priorities.

This is a min-priority queue, where a has “higher priority” than b if a < b.

See also

SimplePriorityQueue.
Show on GitHub

  • The type of data in the underlying binary heap.

    Declaration

    Swift

    public typealias Element = PriorityQueueElement<Priority, Payload>
    Show on GitHub

  • The heap data structure containing our priority queue.

    Declaration

    Swift

    public var heap: Heap
    Show on GitHub

  • Undocumented

    Declaration

    Swift

    public init(heap: Heap, locations: ElementLocations)
    Show on GitHub
  • top

    The data at the top of the priority queue.

    Declaration

    Swift

    public var top: Payload? { get }
    Show on GitHub

  • Removes and returns the top of self.

    Declaration

    Swift

    @discardableResult
public mutating func pop() -> Element?
    Show on GitHub

  • Adds element into self and updates the internal data structures to maintain efficiency.

    Declaration

    Swift

    public mutating func push(_ element: Element)
    Show on GitHub

  • Adds payload into self at priority level priority, and updates the internal data structures to maintain efficiency.

    Declaration

    Swift

    public mutating func push(_ payload: Payload, at priority: Priority)
    Show on GitHub

Priority Queue

Available where Heap: DefaultInitializable, ElementLocations: DefaultInitializable

Available where ElementLocations: DefaultInitializable

  • Constructs a GenericPriorityQueue from heap.

    Precondition

    heap.isMinHeap

    Declaration

    Swift

    public init(_ heap: Heap)
    Show on GitHub

Available where ElementLocations: IndexProtocol

  • Updates the priority of payload to newPriority.

    Precondition

    payload is contained within self.

    Complexity

    O(log n)

    Declaration

    Swift

    @discardableResult
public mutating func update(_ payload: Payload, withNewPriority newPriority: Priority) -> Priority

    Return Value

    the previous priority of elem.

    Show on GitHub