nx_sketch_min_heap.nx
buildroot/runtime/nx_sketch_min_heap.nx
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
imports: nx_syscalls.nxnx_sketch_types.nx
imported by: nobody (leaf or entry point)
structs
| 36 | struct HeapEntry |
| 41 | struct MinHeap |
consts
| 33 | const NX_HEAP_MIN_CAP: i64 = 4 |
| 34 | const NX_HEAP_MAX_CAP: i64 = 1000000 |
functions
| 49 | func nx_heap_alloc(capacity: i64) -> *MinHeap calls 1: sys_mmap |
| 61 | func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry |
| 67 | func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64 |
| 79 | func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64 |
| 100 | func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64 |
| 130 | func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64 |
| 140 | func nx_heap_peek_key(h: *MinHeap) -> i64 calls 1: nx_heap_entry_at |
| 146 | func nx_heap_peek_value(h: *MinHeap) -> i64 calls 1: nx_heap_entry_at |
| 154 | func nx_heap_pop(h: *MinHeap) -> i64 |
| 175 | func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64 |
| 191 | func nx_heap_size(h: *MinHeap) -> i64 |
| 195 | func nx_heap_clear(h: *MinHeap) -> i64 |
| 200 | func nx_heap_memory_bytes(h: *MinHeap) -> i64 |