Zafu/Collection/Heap

source code:

• src/Zafu/Collection/Heap.bosatsu

public dependencies: Zafu/Abstract/Eq, Zafu/Abstract/Foldable, Zafu/Abstract/Ord

Index

• Types: Heap
• Values: combine, combine_assume_same_order, empty, eq, foldable_Heap, foldl, from_List, insert, is_empty, min, ord, pop_min, singleton, size, to_List

Types

Heap[a]

Pairing heap with ordering owned by each heap value.

type Heap[a: *]

Values

combine

Combines two heaps. For non-empty heaps this rebuilds the right side under the left ordering to preserve correctness when orderings differ.

references: Heap

def combine[a](heap: Heap[a], other: Heap[a]) -> Heap[a]

combine_assume_same_order

Fast O(1) meld for heaps that share the same effective ordering. If orderings differ, results are still memory-safe but may be incorrect.

references: Heap

def combine_assume_same_order[a](heap: Heap[a], other: Heap[a]) -> Heap[a]

empty

Empty heap for a chosen ordering.

references: Heap, Zafu/Abstract/Ord::Ord

def empty[a](ord: Zafu/Abstract/Ord::Ord[a]) -> Heap[a]

eq

references: Heap, Zafu/Abstract/Eq::Eq

def eq[a](inst: Zafu/Abstract/Eq::Eq[a]) -> Zafu/Abstract/Eq::Eq[Heap[a]]

foldable_Heap

references: Heap, Zafu/Abstract/Foldable::Foldable

foldable_Heap: Zafu/Abstract/Foldable::Foldable[Heap]

foldl

Fold in min-to-max order.

references: Heap

def foldl[a, b](heap: Heap[a], init: b, fn: (b, a) -> b) -> b

from_List

Builds a heap with pairwise rounds to avoid one-sided insertion chains.

references: Heap, List, Zafu/Abstract/Ord::Ord

def from_List[a](ord: Zafu/Abstract/Ord::Ord[a], items: List[a]) -> Heap[a]

insert

Inserts one item in O(1) amortized by linking with a singleton root.

references: Heap

def insert[a](heap: Heap[a], item: a) -> Heap[a]

is_empty

True if heap has no elements.

references: Bool, Heap

def is_empty[a](heap: Heap[a]) -> Bool

min

Returns the minimum element, if present.

references: Heap, Option

def min[a](heap: Heap[a]) -> Option[a]

ord

references: Heap, Zafu/Abstract/Ord::Ord

def ord[a](inst: Zafu/Abstract/Ord::Ord[a]) -> Zafu/Abstract/Ord::Ord[Heap[a]]

pop_min

Remove minimum and rebuild remainder via two-pass child pairing.

references: Heap, Option, Tuple2

def pop_min[a](heap: Heap[a]) -> Option[(a, Heap[a])]

singleton

Single-element heap.

references: Heap, Zafu/Abstract/Ord::Ord

def singleton[a](ord: Zafu/Abstract/Ord::Ord[a], item: a) -> Heap[a]

size

O(1) cached size.

references: Heap, Int

def size[a](heap: Heap[a]) -> Int

to_List

Ascending list view from repeated pop_min.

references: Heap, List

def to_List[a](heap: Heap[a]) -> List[a]