heap.nx source
↩ module page · 140 lines · 4071 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
20import "syscalls.nx"
21
22struct MinHeap {
23 keys: *i64, // priority keys
24 vals: *i64, // associated payloads
25 size: i64,
26 cap: i64,
27}
28
29func minheap_new(cap: i64) -> *MinHeap {
30 let raw: *u8 = sys_mmap(64)
31 let h: *MinHeap = raw as *MinHeap
32 h.keys = sys_mmap(cap * 8 + 16) as *i64
33 h.vals = sys_mmap(cap * 8 + 16) as *i64
34 h.size = 0
35 h.cap = cap
36 return h
37}
38
39// Swap two heap entries.
40func mh_swap(h: *MinHeap, i: i64, j: i64) -> i64 {
41 let tk: i64 = h.keys[i]
42 let tv: i64 = h.vals[i]
43 h.keys[i] = h.keys[j]
44 h.vals[i] = h.vals[j]
45 h.keys[j] = tk
46 h.vals[j] = tv
47 return 0
48}
49
50// Bubble element at `i` up toward the root while it's smaller
51// than its parent.
52func mh_sift_up(h: *MinHeap, i: i64) -> i64 {
53 var idx: i64 = i
54 while idx > 0 {
55 let parent: i64 = (idx - 1) / 2
56 if h.keys[idx] >= h.keys[parent] { return 0 }
57 mh_swap(h, idx, parent)
58 idx = parent
59 }
60 return 0
61}
62
63// Sift element at `i` down toward leaves while it's larger than
64// either child.
65func mh_sift_down(h: *MinHeap, i: i64) -> i64 {
66 var idx: i64 = i
67 while 1 == 1 {
68 let left: i64 = 2 * idx + 1
69 let right: i64 = 2 * idx + 2
70 var smallest: i64 = idx
71 if left < h.size {
72 if h.keys[left] < h.keys[smallest] { smallest = left }
73 }
74 if right < h.size {
75 if h.keys[right] < h.keys[smallest] { smallest = right }
76 }
77 if smallest == idx { return 0 }
78 mh_swap(h, idx, smallest)
79 idx = smallest
80 }
81 return 0
82}
83
84// Insert (key, value). Returns 0 on success, -1 if cap exceeded.
85func minheap_insert(h: *MinHeap, key: i64, val: i64) -> i64 {
86 if h.size >= h.cap { return -1 }
87 h.keys[h.size] = key
88 h.vals[h.size] = val
89 h.size = h.size + 1
90 mh_sift_up(h, h.size - 1)
91 return 0
92}
93
94// Peek the minimum key without removing. Caller checks h.size > 0.
95func minheap_peek_key(h: *MinHeap) -> i64 {
96 return h.keys[0]
97}
98
99func minheap_peek_val(h: *MinHeap) -> i64 {
100 return h.vals[0]
101}
102
103// Extract the minimum. Writes (key, val) to out slots. Returns
104// 0 on success, -1 if heap is empty.
105func minheap_extract(h: *MinHeap, key_out: *i64, val_out: *i64) -> i64 {
106 if h.size == 0 { return -1 }
107 *key_out = h.keys[0]
108 *val_out = h.vals[0]
109 h.size = h.size - 1
110 if h.size > 0 {
111 h.keys[0] = h.keys[h.size]
112 h.vals[0] = h.vals[h.size]
113 mh_sift_down(h, 0)
114 }
115 return 0
116}
117
118// Compile-only smoke: insert (3, 30), (1, 10), (2, 20); extract
119// in min-key order should be 1, 2, 3.
120func main() -> i64 {
121 let h: *MinHeap = minheap_new(16)
122 minheap_insert(h, 3, 30)
123 minheap_insert(h, 1, 10)
124 minheap_insert(h, 2, 20)
125 if h.size != 3 { return 1 }
126
127 let k: *i64 = sys_mmap(16) as *i64
128 let v: *i64 = sys_mmap(16) as *i64
129
130 minheap_extract(h, k, v)
131 if *k != 1 { return 2 }
132 if *v != 10 { return 3 }
133
134 minheap_extract(h, k, v)
135 if *k != 2 { return 4 }
136
137 minheap_extract(h, k, v)
138 if *k != 3 { return 5 }
139 return 0
140}