nx_heap.nx source
↩ module page · 146 lines · 4185 B
1// heap.nx -- binary min-heap (priority queue).
2//
3// O(log n) insert + extract-min. Used for: event scheduling
4// (timer queues), Dijkstra's shortest path, A* search, top-K
5// selection, garbage-collected memory tracing.
6//
7// Stores i64 keys with associated i64 values (use as priority +
8// payload pointers cast to i64 for richer payloads).
9//
10// Invariants:
11// H1 Min element is always at index 0.
12// H2 For node at index i, children at 2i+1 and 2i+2; parent
13// at (i-1)/2. Standard implicit-tree layout.
14// H3 Insert grows when capacity would be exceeded -- realloc
15// to 2x current. We don't realloc today (NishiLang sys_mmap
16// is one-shot); caller picks initial cap big enough.
17// H4 Stable for equal priorities is NOT guaranteed; insertion
18// order may not be preserved among same-key entries.
19
20// nx_safety_envelope:
21// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
22// sil_target: SIL1
23// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
24// verdict: NOT_YET_EVALUATED
25
26import "nx_syscalls.nx"
27
28struct MinHeap {
29 keys: *i64, // priority keys
30 vals: *i64, // associated payloads
31 size: i64,
32 cap: i64,
33}
34
35func minheap_new(cap: i64) -> *MinHeap {
36 let raw: *u8 = sys_mmap(64)
37 let h: *MinHeap = raw as *MinHeap
38 h.keys = sys_mmap(cap * 8 + 16) as *i64
39 h.vals = sys_mmap(cap * 8 + 16) as *i64
40 h.size = 0
41 h.cap = cap
42 return h
43}
44
45// Swap two heap entries.
46func mh_swap(h: *MinHeap, i: i64, j: i64) -> i64 {
47 let tk: i64 = h.keys[i]
48 let tv: i64 = h.vals[i]
49 h.keys[i] = h.keys[j]
50 h.vals[i] = h.vals[j]
51 h.keys[j] = tk
52 h.vals[j] = tv
53 return 0
54}
55
56// Bubble element at `i` up toward the root while it's smaller
57// than its parent.
58func mh_sift_up(h: *MinHeap, i: i64) -> i64 {
59 var idx: i64 = i
60 while idx > 0 {
61 let parent: i64 = (idx - 1) / 2
62 if h.keys[idx] >= h.keys[parent] { return 0 }
63 mh_swap(h, idx, parent)
64 idx = parent
65 }
66 return 0
67}
68
69// Sift element at `i` down toward leaves while it's larger than
70// either child.
71func mh_sift_down(h: *MinHeap, i: i64) -> i64 {
72 var idx: i64 = i
73 while 1 == 1 {
74 let left: i64 = 2 * idx + 1
75 let right: i64 = 2 * idx + 2
76 var smallest: i64 = idx
77 if left < h.size {
78 if h.keys[left] < h.keys[smallest] { smallest = left }
79 }
80 if right < h.size {
81 if h.keys[right] < h.keys[smallest] { smallest = right }
82 }
83 if smallest == idx { return 0 }
84 mh_swap(h, idx, smallest)
85 idx = smallest
86 }
87 return 0
88}
89
90// Insert (key, value). Returns 0 on success, -1 if cap exceeded.
91func minheap_insert(h: *MinHeap, key: i64, val: i64) -> i64 {
92 if h.size >= h.cap { return -1 }
93 h.keys[h.size] = key
94 h.vals[h.size] = val
95 h.size = h.size + 1
96 mh_sift_up(h, h.size - 1)
97 return 0
98}
99
100// Peek the minimum key without removing. Caller checks h.size > 0.
101func minheap_peek_key(h: *MinHeap) -> i64 {
102 return h.keys[0]
103}
104
105func minheap_peek_val(h: *MinHeap) -> i64 {
106 return h.vals[0]
107}
108
109// Extract the minimum. Writes (key, val) to out slots. Returns
110// 0 on success, -1 if heap is empty.
111func minheap_extract(h: *MinHeap, key_out: *i64, val_out: *i64) -> i64 {
112 if h.size == 0 { return -1 }
113 *key_out = h.keys[0]
114 *val_out = h.vals[0]
115 h.size = h.size - 1
116 if h.size > 0 {
117 h.keys[0] = h.keys[h.size]
118 h.vals[0] = h.vals[h.size]
119 mh_sift_down(h, 0)
120 }
121 return 0
122}
123
124// Compile-only smoke: insert (3, 30), (1, 10), (2, 20); extract
125// in min-key order should be 1, 2, 3.
126func main() -> i64 {
127 let h: *MinHeap = minheap_new(16)
128 minheap_insert(h, 3, 30)
129 minheap_insert(h, 1, 10)
130 minheap_insert(h, 2, 20)
131 if h.size != 3 { return 1 }
132
133 let k: *i64 = sys_mmap(16) as *i64
134 let v: *i64 = sys_mmap(16) as *i64
135
136 minheap_extract(h, k, v)
137 if *k != 1 { return 2 }
138 if *v != 10 { return 3 }
139
140 minheap_extract(h, k, v)
141 if *k != 2 { return 4 }
142
143 minheap_extract(h, k, v)
144 if *k != 3 { return 5 }
145 return 0
146}