• Effekt Logo Effekt Library
    • heap
      • Weighted
      • internal
        • Tree
          • Node
          • Empty
        • mergePairs
      • Heap
      • empty
      • single
      • isEmpty
      • meld
      • insert
      • findMinimum
      • extract
      • exchange
      • each
      • collectHeap
    • heap
      • Jump to source: libraries/common/heap.effekt
      Example usage: examples/stdlib/heap
      • Weighted [A] (value: A, weight: Double)
        • A value together with its priority. Smaller weights come first.
      • internal
        • Tree [A]
          • A pairing heap: empty, or a minimal element with its subheaps.
          • Node (value: A, weight: Double, subheaps: List[Tree[A]])
          • Empty
        • mergePairs [A] (heap: Tree[A], heaps: List[Tree[A]]): Tree[A] / {} 
          • Merge a nonempty list of heaps, given as head and tail, using the two-pass pairing strategy.

O(log n) amortized
      • Heap [A]
        • Persistent min-heap, implemented as a pairing heap.
      • empty [A]: Heap[A] / {} 
        • The empty heap.

O(1)
      • single [A] (value: A, weight: Double): Heap[A] / {} 
        • A heap containing exactly one element.

O(1)
      • isEmpty [A] (heap: Heap[A]): Bool / {} 
        • Check if the heap is empty.

O(1)
      • meld [A] (heap1: Heap[A], heap2: Heap[A]): Heap[A] / {} 
        • Merge two heaps.

O(1)
      • insert [A] (heap: Heap[A], value: A, weight: Double): Heap[A] / {} 
        • Insert a value with the given weight.

O(1)
      • findMinimum [A] (heap: Heap[A]): Option[Weighted[A]] / {} 
        • The element with the smallest weight, without removing it.
Returns `None()` if the heap is empty.

O(1)
      • extract [A] (heap: Heap[A]): Option[Tuple2[Weighted[A], Heap[A]]] / {} 
        • Remove the element with the smallest weight, returning it and the remaining heap.
Returns `None()` if the heap is empty.

O(log n) amortized
      • exchange [A] (heap: Heap[A], value: A, weight: Double): Tuple2[Weighted[A], Heap[A]] / {} 
        • Insert the given value and remove the element with the smallest weight.
Returns the given value and the unchanged heap if its weight is not larger than all others.

O(log n) amortized
      • each [A] (heap: Heap[A]): Unit / {emit[Weighted[A]]} 
        • Emit all elements in ascending order of weight.

O(n log n)
      • collectHeap [A] { stream: => Unit / {emit[Weighted[A]]} }: Heap[A] / {} 
        • Collect all emitted elements into a heap.

O(n)