Heap

public class Heap<Element>

Heap: Generic priority queue with custom ordering and fixed capacity.

Provides a binary-heap implementation backed by a Swift Array, supporting a caller-supplied comparison closure to define ordering. Offers convenience builders for min/max heaps when Element: Comparable.

  • Features:

    • Fixed logical capacity with optional force-insert semantics when full
    • Event callbacks for insert/remove/move to track external indices
    • O(log n) insertion and removal; O(1) root access

  • Thread-safety: Not synchronized; guard with external synchronization when needed.

  • Callback triggered on insert, remove, and index changes.

    Useful for synchronizing an external index stored alongside elements. The callback is invoked after structural mutations and moves.

    Declaration

    Swift

    public var onEvent: ((Event) -> Void)?

  • The root element (highest priority), or nil if heap is empty.

    Declaration

    Swift

    public var root: Element? { get }

  • All elements currently in the heap.

    Declaration

    Swift

    public var elements: [Element] { get }

  • Initializes a heap with given capacity and comparison strategy.

    Declaration

    Swift

    public required init(capacity: Int, compare: @escaping (Element, Element) -> ComparisonResult)

    Parameters

    capacity

    Maximum number of elements the heap can logically store. Negative values are treated as 0.
    compare

    Comparison function returning a ComparisonResult indicating relative priority.

Public Heap Operations

  • Inserts an element.

    When the heap is not full, the element is appended then sifted to restore the heap property. When the heap is full, behavior depends on force and the comparison with the current root:

    • force == false: Only allows replacement when compare(element, root) == .moreBottom (lower priority than root); otherwise the insertion is rejected and the input element is returned.

    • force == true: Allows replacement unless compare(element, root) == .moreTop (higher priority than root); in that case the insertion is rejected and the input element is returned.

    Declaration

    Swift

    @discardableResult
func insert(_ element: Element, force: Bool = false) -> Element?

    Parameters

    element

    Element to insert
    force

    Force-insert semantics when heap is full (default: false)

    Return Value

    Displaced root when a replacement occurs; the input element when rejected; otherwise nil

  • Removes and returns an element at the specified index (default: root).

    Declaration

    Swift

    @discardableResult
func remove(at index: Int = 0) -> Element?

    Parameters

    index

    Index of element to remove (defaults to root at index 0)

    Return Value

    Removed element, or nil if index is invalid or heap is empty

Event & Comparison Enums

  • Heap event used for notifications.

    See more

    Declaration

    Swift

    enum Event

  • Relative priority between two elements.

    See more

    Declaration

    Swift

    enum ComparisonResult

Available where Element: Comparable

  • Returns a max heap (largest elements at root).

    Declaration

    Swift

    static func maxHeap(capacity: Int) -> Self

  • Returns a min heap (smallest elements at root).

    Declaration

    Swift

    static func minHeap(capacity: Int) -> Self