heap.nx
buildroot/runtime/heap.nx
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
imports: syscalls.nx
imported by: nobody (leaf or entry point)
call flow from main pre-order; caps 40 nodes / depth 6 declared; ↻ = already shown
structs
| 22 | struct MinHeap { |
consts
| none |
functions
| 29 | func minheap_new(cap: i64) -> *MinHeap {
called by 1: main |
| 40 | func mh_swap(h: *MinHeap, i: i64, j: i64) -> i64 { |
| 52 | func mh_sift_up(h: *MinHeap, i: i64) -> i64 { |
| 65 | func mh_sift_down(h: *MinHeap, i: i64) -> i64 { |
| 85 | func minheap_insert(h: *MinHeap, key: i64, val: i64) -> i64 { |
| 95 | func minheap_peek_key(h: *MinHeap) -> i64 { |
| 99 | func minheap_peek_val(h: *MinHeap) -> i64 { |
| 105 | func minheap_extract(h: *MinHeap, key_out: *i64, val_out: *i64) -> i64 { |
| 120 | func main() -> i64 { |