sketch_min_heap.nx source
↩ module page · 196 lines · 5760 B
1// sketch_min_heap.nx -- binary min-heap (priority queue) primitive.
2//
3// Foundational data structure many sketch algorithms compose against:
4// - top-K queries (heap of size K, evict-max if heap-min > new)
5// - Dijkstra / A* (heap of (cost, node) pairs)
6// - Huffman coding (heap of node weights)
7// - merging sorted streams (heap of stream heads)
8//
9// Array-backed binary heap. parent(i) = (i-1)/2; children = 2i+1, 2i+2.
10// Push: append at end, sift up. Pop: swap root with last, shrink,
11// sift down. Both O(log n).
12//
13// API stores (key, value) pairs where ORDER is by key (i64). For
14// max-heap behavior, negate keys at the caller boundary.
15//
16// LOSSLESS-LANGUAGE DISCIPLINE:
17// This primitive is EXACT (no approximation). Production tier.
18// No envelope returned because there's nothing to bound -- caller
19// accesses raw values. This is a foundational data-structure
20// primitive, not an estimator.
21//
22// MaturityClass = Production.
23
24import "syscalls.nx"
25import "sketch_types.nx"
26
27const NX_HEAP_MIN_CAP: i64 = 4
28const NX_HEAP_MAX_CAP: i64 = 1000000
29
30struct HeapEntry {
31 key: i64,
32 value: i64,
33}
34
35struct MinHeap {
36 entries: *HeapEntry,
37 capacity: i64,
38 size: i64,
39}
40
41// === construction =================================================
42
43func nx_heap_alloc(capacity: i64) -> *MinHeap {
44 if capacity < NX_HEAP_MIN_CAP { return 0 as *MinHeap }
45 if capacity > NX_HEAP_MAX_CAP { return 0 as *MinHeap }
46 let raw: *u8 = sys_mmap(40)
47 let h: *MinHeap = raw as *MinHeap
48 let entries_raw: *u8 = sys_mmap(capacity * 16)
49 h.entries = entries_raw as *HeapEntry
50 h.capacity = capacity
51 h.size = 0
52 return h
53}
54
55func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry {
56 return (h.entries as i64 + i * 16) as *HeapEntry
57}
58
59// === sift up + sift down ==========================================
60
61func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64 {
62 let ea: *HeapEntry = nx_heap_entry_at(h, a)
63 let eb: *HeapEntry = nx_heap_entry_at(h, b)
64 let tk: i64 = ea.key
65 let tv: i64 = ea.value
66 ea.key = eb.key
67 ea.value = eb.value
68 eb.key = tk
69 eb.value = tv
70 return 0
71}
72
73func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64 {
74 var cur: i64 = i
75 var done: i64 = 0
76 while done == 0 {
77 if cur == 0 { done = 1 }
78 if done == 0 {
79 let parent: i64 = (cur - 1) / 2
80 let pe: *HeapEntry = nx_heap_entry_at(h, parent)
81 let ce: *HeapEntry = nx_heap_entry_at(h, cur)
82 if pe.key <= ce.key {
83 done = 1
84 }
85 if done == 0 {
86 nx_heap_swap(h, cur, parent)
87 cur = parent
88 }
89 }
90 }
91 return 0
92}
93
94func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64 {
95 var cur: i64 = i
96 var done: i64 = 0
97 while done == 0 {
98 let lc: i64 = 2 * cur + 1
99 let rc: i64 = 2 * cur + 2
100 var smallest: i64 = cur
101 if lc < h.size {
102 let lce: *HeapEntry = nx_heap_entry_at(h, lc)
103 let se: *HeapEntry = nx_heap_entry_at(h, smallest)
104 if lce.key < se.key { smallest = lc }
105 }
106 if rc < h.size {
107 let rce: *HeapEntry = nx_heap_entry_at(h, rc)
108 let se: *HeapEntry = nx_heap_entry_at(h, smallest)
109 if rce.key < se.key { smallest = rc }
110 }
111 if smallest == cur {
112 done = 1
113 }
114 if done == 0 {
115 nx_heap_swap(h, cur, smallest)
116 cur = smallest
117 }
118 }
119 return 0
120}
121
122// === push / pop / peek ============================================
123
124func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64 {
125 if h.size >= h.capacity { return -1 }
126 let e: *HeapEntry = nx_heap_entry_at(h, h.size)
127 e.key = key
128 e.value = value
129 h.size = h.size + 1
130 nx_heap_sift_up(h, h.size - 1)
131 return 0
132}
133
134func nx_heap_peek_key(h: *MinHeap) -> i64 {
135 if h.size == 0 { return 0 }
136 let e: *HeapEntry = nx_heap_entry_at(h, 0)
137 return e.key
138}
139
140func nx_heap_peek_value(h: *MinHeap) -> i64 {
141 if h.size == 0 { return 0 }
142 let e: *HeapEntry = nx_heap_entry_at(h, 0)
143 return e.value
144}
145
146// Pop returns 0 on success, -1 if empty. Caller reads root via
147// peek BEFORE calling pop.
148func nx_heap_pop(h: *MinHeap) -> i64 {
149 if h.size == 0 { return -1 }
150 if h.size == 1 {
151 h.size = 0
152 return 0
153 }
154 let last: *HeapEntry = nx_heap_entry_at(h, h.size - 1)
155 let root: *HeapEntry = nx_heap_entry_at(h, 0)
156 root.key = last.key
157 root.value = last.value
158 h.size = h.size - 1
159 nx_heap_sift_down(h, 0)
160 return 0
161}
162
163// === top-K replacement convenience ===============================
164//
165// For top-K-MAX use case: heap of size K storing the K largest keys
166// seen so far. When new key arrives: if heap full and new > min,
167// replace root + sift down. Returns 1 if installed, 0 if rejected.
168
169func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64 {
170 if h.size < h.capacity {
171 nx_heap_push(h, key, value)
172 return 1
173 }
174 // At cap: replace root if new key > root key.
175 let root: *HeapEntry = nx_heap_entry_at(h, 0)
176 if key <= root.key { return 0 }
177 root.key = key
178 root.value = value
179 nx_heap_sift_down(h, 0)
180 return 1
181}
182
183// === introspection ================================================
184
185func nx_heap_size(h: *MinHeap) -> i64 {
186 return h.size
187}
188
189func nx_heap_clear(h: *MinHeap) -> i64 {
190 h.size = 0
191 return 0
192}
193
194func nx_heap_memory_bytes(h: *MinHeap) -> i64 {
195 return 40 + h.capacity * 16
196}