nx_sketch_min_heap.nx source
↩ module page · 202 lines · 5821 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
24// nx_safety_envelope:
25// intended_use: AUTO_APPLIED -- primitive-specific tuning queued
26// sil_target: SIL1
27// evidence: [bulk_applied_2026-05-16, see-file-comment-for-detail]
28// verdict: NOT_YET_EVALUATED
29
30import "nx_syscalls.nx"
31import "nx_sketch_types.nx"
32
33const NX_HEAP_MIN_CAP: i64 = 4
34const NX_HEAP_MAX_CAP: i64 = 1000000
35
36struct HeapEntry {
37 key: i64,
38 value: i64,
39}
40
41struct MinHeap {
42 entries: *HeapEntry,
43 capacity: i64,
44 size: i64,
45}
46
47// === construction =================================================
48
49func nx_heap_alloc(capacity: i64) -> *MinHeap {
50 if capacity < NX_HEAP_MIN_CAP { return 0 as *MinHeap }
51 if capacity > NX_HEAP_MAX_CAP { return 0 as *MinHeap }
52 let raw: *u8 = sys_mmap(40)
53 let h: *MinHeap = raw as *MinHeap
54 let entries_raw: *u8 = sys_mmap(capacity * 16)
55 h.entries = entries_raw as *HeapEntry
56 h.capacity = capacity
57 h.size = 0
58 return h
59}
60
61func nx_heap_entry_at(h: *MinHeap, i: i64) -> *HeapEntry {
62 return (h.entries as i64 + i * 16) as *HeapEntry
63}
64
65// === sift up + sift down ==========================================
66
67func nx_heap_swap(h: *MinHeap, a: i64, b: i64) -> i64 {
68 let ea: *HeapEntry = nx_heap_entry_at(h, a)
69 let eb: *HeapEntry = nx_heap_entry_at(h, b)
70 let tk: i64 = ea.key
71 let tv: i64 = ea.value
72 ea.key = eb.key
73 ea.value = eb.value
74 eb.key = tk
75 eb.value = tv
76 return 0
77}
78
79func nx_heap_sift_up(h: *MinHeap, i: i64) -> i64 {
80 var cur: i64 = i
81 var done: i64 = 0
82 while done == 0 {
83 if cur == 0 { done = 1 }
84 if done == 0 {
85 let parent: i64 = (cur - 1) / 2
86 let pe: *HeapEntry = nx_heap_entry_at(h, parent)
87 let ce: *HeapEntry = nx_heap_entry_at(h, cur)
88 if pe.key <= ce.key {
89 done = 1
90 }
91 if done == 0 {
92 nx_heap_swap(h, cur, parent)
93 cur = parent
94 }
95 }
96 }
97 return 0
98}
99
100func nx_heap_sift_down(h: *MinHeap, i: i64) -> i64 {
101 var cur: i64 = i
102 var done: i64 = 0
103 while done == 0 {
104 let lc: i64 = 2 * cur + 1
105 let rc: i64 = 2 * cur + 2
106 var smallest: i64 = cur
107 if lc < h.size {
108 let lce: *HeapEntry = nx_heap_entry_at(h, lc)
109 let se: *HeapEntry = nx_heap_entry_at(h, smallest)
110 if lce.key < se.key { smallest = lc }
111 }
112 if rc < h.size {
113 let rce: *HeapEntry = nx_heap_entry_at(h, rc)
114 let se: *HeapEntry = nx_heap_entry_at(h, smallest)
115 if rce.key < se.key { smallest = rc }
116 }
117 if smallest == cur {
118 done = 1
119 }
120 if done == 0 {
121 nx_heap_swap(h, cur, smallest)
122 cur = smallest
123 }
124 }
125 return 0
126}
127
128// === push / pop / peek ============================================
129
130func nx_heap_push(h: *MinHeap, key: i64, value: i64) -> i64 {
131 if h.size >= h.capacity { return -1 }
132 let e: *HeapEntry = nx_heap_entry_at(h, h.size)
133 e.key = key
134 e.value = value
135 h.size = h.size + 1
136 nx_heap_sift_up(h, h.size - 1)
137 return 0
138}
139
140func nx_heap_peek_key(h: *MinHeap) -> i64 {
141 if h.size == 0 { return 0 }
142 let e: *HeapEntry = nx_heap_entry_at(h, 0)
143 return e.key
144}
145
146func nx_heap_peek_value(h: *MinHeap) -> i64 {
147 if h.size == 0 { return 0 }
148 let e: *HeapEntry = nx_heap_entry_at(h, 0)
149 return e.value
150}
151
152// Pop returns 0 on success, -1 if empty. Caller reads root via
153// peek BEFORE calling pop.
154func nx_heap_pop(h: *MinHeap) -> i64 {
155 if h.size == 0 { return -1 }
156 if h.size == 1 {
157 h.size = 0
158 return 0
159 }
160 let last: *HeapEntry = nx_heap_entry_at(h, h.size - 1)
161 let root: *HeapEntry = nx_heap_entry_at(h, 0)
162 root.key = last.key
163 root.value = last.value
164 h.size = h.size - 1
165 nx_heap_sift_down(h, 0)
166 return 0
167}
168
169// === top-K replacement convenience ===============================
170//
171// For top-K-MAX use case: heap of size K storing the K largest keys
172// seen so far. When new key arrives: if heap full and new > min,
173// replace root + sift down. Returns 1 if installed, 0 if rejected.
174
175func nx_heap_top_k_offer(h: *MinHeap, key: i64, value: i64) -> i64 {
176 if h.size < h.capacity {
177 nx_heap_push(h, key, value)
178 return 1
179 }
180 // At cap: replace root if new key > root key.
181 let root: *HeapEntry = nx_heap_entry_at(h, 0)
182 if key <= root.key { return 0 }
183 root.key = key
184 root.value = value
185 nx_heap_sift_down(h, 0)
186 return 1
187}
188
189// === introspection ================================================
190
191func nx_heap_size(h: *MinHeap) -> i64 {
192 return h.size
193}
194
195func nx_heap_clear(h: *MinHeap) -> i64 {
196 h.size = 0
197 return 0
198}
199
200func nx_heap_memory_bytes(h: *MinHeap) -> i64 {
201 return 40 + h.capacity * 16
202}