sketch_min_heap.nx
buildroot/runtime/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 · 3 importers
imports: syscalls.nxsketch_types.nx
imported by: nx_graphalg.nxnx_sort.nxsketch_min_heap_test.nx
structs
| 30 | struct HeapEntry { |
| 35 | struct MinHeap { |
consts
| 27 | const NX_HEAP_MIN_CAP: i64 = 4 |
| 28 | const NX_HEAP_MAX_CAP: i64 = 1000000 |
functions
| 43 | func nx_heap_alloc(capacity: i64) -> *MinHeap { |
| 55 | func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry { |
| 61 | func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64 { |
| 73 | func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64 { |
| 94 | func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64 { |
| 124 | func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64 {
called by 4: nx_graphalg_dijkstranx_sort_heapnx_heap_top_k_offermain calls 2: nx_heap_entry_atnx_heap_sift_up |
| 134 | func nx_heap_peek_key(h: *MinHeap) -> i64 { |
| 140 | func nx_heap_peek_value(h: *MinHeap) -> i64 { |
| 148 | func nx_heap_pop(h: *MinHeap) -> i64 { |
| 169 | func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64 { |
| 185 | func nx_heap_size(h: *MinHeap) -> i64 { |
| 189 | func nx_heap_clear(h: *MinHeap) -> i64 {
called by 1: main |
| 194 | func nx_heap_memory_bytes(h: *MinHeap) -> i64 { |