code wiki / (root) / sketch_min_heap.nx

sketch_min_heap.nx

buildroot/runtime/sketch_min_heap.nx

5760 B196 linesdepth 4pulls 4 transitivereach 6 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 · 3 importers

syscalls.nx sketch_types.nx sketch_min_heap.nx nx_graphalg.nx nx_sort.nx sketch_min_heap_test.nx

imports: syscalls.nxsketch_types.nx

imported by: nx_graphalg.nxnx_sort.nxsketch_min_heap_test.nx

structs

30struct HeapEntry {
35struct MinHeap {

consts

27const NX_HEAP_MIN_CAP: i64 = 4
28const NX_HEAP_MAX_CAP: i64 = 1000000

functions

43func nx_heap_alloc(capacity: i64) -> *MinHeap {
55func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry {
61func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64 {
73func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64 {
94func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64 {
124func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64 {
134func nx_heap_peek_key(h: *MinHeap) -> i64 {
140func nx_heap_peek_value(h: *MinHeap) -> i64 {
148func nx_heap_pop(h: *MinHeap) -> i64 {
169func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64 {
185func nx_heap_size(h: *MinHeap) -> i64 {
189func nx_heap_clear(h: *MinHeap) -> i64 {
called by 1: main
194func nx_heap_memory_bytes(h: *MinHeap) -> i64 {