Heap

public struct Heap<T> : Collection where T : Comparable

Min (default) or max heap. A heap is a tree-based data structure that can be used to efficiently implement a priority queue. It gives O(1) read (peek) access to the min or max value, and can be updated via a pop or push in O(log(n)) time. Removing an arbitrary element takes O(n) time.

var pq = Heap<Int>(isMin: false, startingValues: [5, -1, 3, 42, 68, 99, 72])     // Max heap
pq.isEmpty                 // false
pq.count                   // 7
let max = pq.pop()         // max = 99, removes 99 from the heap
let currentMax = pq.peek() // currentMax = 72, leaves heap the same
pq.push(100)               // Adds 100 to the heap
pq.peek()                  // 100
pq.contains(3)             // true
pq.push(3)                 // Adds another 3
pq.remove(3)               // Removes one of the 3's from the heap
pq.push(-1)                // Adds another -1
pq.removeAll(-1)           // Removes both -1's
pq.clear()                 // Removes all values
pq.isEmpty                 // true

  • Declaration

    Swift

    public var startIndex: Int { get }

  • Declaration

    Swift

    public var endIndex: Int { get }

  • Public interface ************************

    Declaration

    Swift

    public init(isMin: Bool = true, startingValues: [T] = [])

  • Push an item onto the heap. Complexity is O(log(n)).

    Declaration

    Swift

    public mutating func push(_ item: T)

    Parameters

    item

    item to add to the heap

  • Remove and return the min or max value from the heap. Complexity is O(log(n)).

    Declaration

    Swift

    @discardableResult
public mutating func pop() -> T?

    Return Value

    optional item (nil if the heap is empty)

  • Return the min or max value of the heap. Complexity is O(1).

    Declaration

    Swift

    public func peek() -> T?

  • Remove the first occurrence of the given item from the heap. Complexity is O(n).

    Declaration

    Swift

    public mutating func remove(_ item: T)

    Parameters

    item

    item to remove

  • Remove all occurrences of the given item from the heap. Complexity is O(n).

    Declaration

    Swift

    public mutating func removeAll(_ item: T)

    Parameters

    item

    item to remove

  • Remove all items from the heap.

    Declaration

    Swift

    public mutating func clear()

  • Declaration

    Swift

    public subscript(pos: Int) -> T { get }

  • Declaration

    Swift

    public func index(after i: Int) -> Int