code wiki / (root) / nx_heap.nx

nx_heap.nx

buildroot/runtime/nx_heap.nx

4185 B146 linesdepth 2pulls 2 transitivereach 0 importersview sourcekind tool
docsdependenciesstructsconstsfunctions

about

heap.nx -- binary min-heap (priority queue). O(log n) insert + extract-min. Used for: event scheduling (timer queues), Dijkstra's shortest path, A* search, top-K selection, garbage-collected memory tracing. Stores i64 keys with associated i64 values (use as priority + payload pointers cast to i64 for richer payloads). Invariants: H1 Min element is always at index 0. H2 For node at index i, children at 2i+1 and 2i+2; parent at (i-1)/2. Standard implicit-tree layout. H3 Insert grows when capacity would be exceeded -- realloc to 2x current. We don't realloc today (NishiLang sys_mmap is one-shot); caller picks initial cap big enough. H4 Stable for equal priorities is NOT guaranteed; insertion order may not be preserved among same-key entries.

dependencies 1 imports · 0 importers

nx_syscalls.nx nx_heap.nx

imports: nx_syscalls.nx

imported by: nobody (leaf or entry point)

call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown

main minheap_new sys_mmap minheap_insert mh_sift_up mh_swap sys_mmap ↻ minheap_extract mh_sift_down mh_swap ↻

structs

28struct MinHeap

consts

none

functions

35func minheap_new(cap: i64) -> *MinHeap
called by 1: main calls 1: sys_mmap
46func mh_swap(h: *MinHeap, i: i64, j: i64) -> i64
58func mh_sift_up(h: *MinHeap, i: i64) -> i64
called by 1: minheap_insert calls 1: mh_swap
71func mh_sift_down(h: *MinHeap, i: i64) -> i64
called by 1: minheap_extract calls 1: mh_swap
91func minheap_insert(h: *MinHeap, key: i64, val: i64) -> i64
called by 1: main calls 1: mh_sift_up
101func minheap_peek_key(h: *MinHeap) -> i64
105func minheap_peek_val(h: *MinHeap) -> i64
111func minheap_extract(h: *MinHeap, key_out: *i64, val_out: *i64) -> i64
called by 1: main calls 1: mh_sift_down
126func main() -> i64