code wiki / (root) / nx_sketch_min_heap.nx

nx_sketch_min_heap.nx

buildroot/runtime/nx_sketch_min_heap.nx

5821 B202 linesdepth 3pulls 3 transitivereach 0 importersview sourcekind sketch/demotopic sketch
docsdependenciesstructsconstsfunctions

about

sketch_min_heap.nx -- binary min-heap (priority queue) primitive. Foundational data structure many sketch algorithms compose against: - top-K queries (heap of size K, evict-max if heap-min > new) - Dijkstra / A* (heap of (cost, node) pairs) - Huffman coding (heap of node weights) - merging sorted streams (heap of stream heads) Array-backed binary heap. parent(i) = (i-1)/2; children = 2i+1, 2i+2. Push: append at end, sift up. Pop: swap root with last, shrink, sift down. Both O(log n). API stores (key, value) pairs where ORDER is by key (i64). For max-heap behavior, negate keys at the caller boundary. LOSSLESS-LANGUAGE DISCIPLINE: This primitive is EXACT (no approximation). Production tier. No envelope returned because there's nothing to bound -- caller accesses raw values. This is a foundational data-structure primitive, not an estimator. MaturityClass = Production.

dependencies 2 imports · 0 importers

nx_syscalls.nx nx_sketch_types.nx nx_sketch_min_heap.nx

imports: nx_syscalls.nxnx_sketch_types.nx

imported by: nobody (leaf or entry point)

structs

36struct HeapEntry
41struct MinHeap

consts

33const NX_HEAP_MIN_CAP: i64 = 4
34const NX_HEAP_MAX_CAP: i64 = 1000000

functions

49func nx_heap_alloc(capacity: i64) -> *MinHeap
calls 1: sys_mmap
61func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry
67func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64
79func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64
100func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64
130func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64
140func nx_heap_peek_key(h: *MinHeap) -> i64
146func nx_heap_peek_value(h: *MinHeap) -> i64
154func nx_heap_pop(h: *MinHeap) -> i64
175func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64
191func nx_heap_size(h: *MinHeap) -> i64
195func nx_heap_clear(h: *MinHeap) -> i64
200func nx_heap_memory_bytes(h: *MinHeap) -> i64