code wiki / (root) / heap.nx

heap.nx

buildroot/runtime/heap.nx

4071 B140 linesdepth 3pulls 3 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

syscalls.nx heap.nx

imports: 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 minheap_insert mh_sift_up mh_swap minheap_extract mh_sift_down mh_swap ↻

structs

22struct MinHeap {

consts

none

functions

29func minheap_new(cap: i64) -> *MinHeap {
called by 1: main
40func mh_swap(h: *MinHeap, i: i64, j: i64) -> i64 {
52func mh_sift_up(h: *MinHeap, i: i64) -> i64 {
called by 1: minheap_insert calls 1: mh_swap
65func mh_sift_down(h: *MinHeap, i: i64) -> i64 {
called by 1: minheap_extract calls 1: mh_swap
85func minheap_insert(h: *MinHeap, key: i64, val: i64) -> i64 {
called by 1: main calls 1: mh_sift_up
95func minheap_peek_key(h: *MinHeap) -> i64 {
99func minheap_peek_val(h: *MinHeap) -> i64 {
105func minheap_extract(h: *MinHeap, key_out: *i64, val_out: *i64) -> i64 {
called by 1: main calls 1: mh_sift_down
120func main() -> i64 {