Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * binaryheap.c
4 : * A simple binary heap implementation
5 : *
6 : * Portions Copyright (c) 2012-2026, PostgreSQL Global Development Group
7 : *
8 : * IDENTIFICATION
9 : * src/common/binaryheap.c
10 : *
11 : *-------------------------------------------------------------------------
12 : */
13 :
14 : #ifdef FRONTEND
15 : #include "postgres_fe.h"
16 : #else
17 : #include "postgres.h"
18 : #endif
19 :
20 : #ifdef FRONTEND
21 : #include "common/logging.h"
22 : #endif
23 : #include "lib/binaryheap.h"
24 :
25 : static void sift_down(binaryheap *heap, int node_off);
26 : static void sift_up(binaryheap *heap, int node_off);
27 :
28 : /*
29 : * binaryheap_allocate
30 : *
31 : * Returns a pointer to a newly-allocated heap that has the capacity to
32 : * store the given number of nodes, with the heap property defined by
33 : * the given comparator function, which will be invoked with the additional
34 : * argument specified by 'arg'.
35 : */
36 : binaryheap *
37 4614 : binaryheap_allocate(int capacity, binaryheap_comparator compare, void *arg)
38 : {
39 : int sz;
40 : binaryheap *heap;
41 :
42 4614 : sz = offsetof(binaryheap, bh_nodes) + sizeof(bh_node_type) * capacity;
43 4614 : heap = (binaryheap *) palloc(sz);
44 4614 : heap->bh_space = capacity;
45 4614 : heap->bh_compare = compare;
46 4614 : heap->bh_arg = arg;
47 :
48 4614 : heap->bh_size = 0;
49 4614 : heap->bh_has_heap_property = true;
50 :
51 4614 : return heap;
52 : }
53 :
54 : /*
55 : * binaryheap_reset
56 : *
57 : * Resets the heap to an empty state, losing its data content but not the
58 : * parameters passed at allocation.
59 : */
60 : void
61 232 : binaryheap_reset(binaryheap *heap)
62 : {
63 232 : heap->bh_size = 0;
64 232 : heap->bh_has_heap_property = true;
65 232 : }
66 :
67 : /*
68 : * binaryheap_free
69 : *
70 : * Releases memory used by the given binaryheap.
71 : */
72 : void
73 4074 : binaryheap_free(binaryheap *heap)
74 : {
75 4074 : pfree(heap);
76 4074 : }
77 :
78 : /*
79 : * These utility functions return the offset of the left child, right
80 : * child, and parent of the node at the given index, respectively.
81 : *
82 : * The heap is represented as an array of nodes, with the root node
83 : * stored at index 0. The left child of node i is at index 2*i+1, and
84 : * the right child at 2*i+2. The parent of node i is at index (i-1)/2.
85 : */
86 :
87 : static inline int
88 19228578 : left_offset(int i)
89 : {
90 19228578 : return 2 * i + 1;
91 : }
92 :
93 : static inline int
94 19228578 : right_offset(int i)
95 : {
96 19228578 : return 2 * i + 2;
97 : }
98 :
99 : static inline int
100 4863520 : parent_offset(int i)
101 : {
102 4863520 : return (i - 1) / 2;
103 : }
104 :
105 : /*
106 : * binaryheap_add_unordered
107 : *
108 : * Adds the given datum to the end of the heap's list of nodes in O(1) without
109 : * preserving the heap property. This is a convenience to add elements quickly
110 : * to a new heap. To obtain a valid heap, one must call binaryheap_build()
111 : * afterwards.
112 : */
113 : void
114 38472 : binaryheap_add_unordered(binaryheap *heap, bh_node_type d)
115 : {
116 38472 : if (heap->bh_size >= heap->bh_space)
117 : {
118 : #ifdef FRONTEND
119 0 : pg_fatal("out of binary heap slots");
120 : #else
121 0 : elog(ERROR, "out of binary heap slots");
122 : #endif
123 : }
124 38472 : heap->bh_has_heap_property = false;
125 38472 : heap->bh_nodes[heap->bh_size] = d;
126 38472 : heap->bh_size++;
127 38472 : }
128 :
129 : /*
130 : * binaryheap_build
131 : *
132 : * Assembles a valid heap in O(n) from the nodes added by
133 : * binaryheap_add_unordered(). Not needed otherwise.
134 : */
135 : void
136 4362 : binaryheap_build(binaryheap *heap)
137 : {
138 : int i;
139 :
140 24940 : for (i = parent_offset(heap->bh_size - 1); i >= 0; i--)
141 20578 : sift_down(heap, i);
142 4362 : heap->bh_has_heap_property = true;
143 4362 : }
144 :
145 : /*
146 : * binaryheap_add
147 : *
148 : * Adds the given datum to the heap in O(log n) time, while preserving
149 : * the heap property.
150 : */
151 : void
152 1882573 : binaryheap_add(binaryheap *heap, bh_node_type d)
153 : {
154 1882573 : if (heap->bh_size >= heap->bh_space)
155 : {
156 : #ifdef FRONTEND
157 0 : pg_fatal("out of binary heap slots");
158 : #else
159 0 : elog(ERROR, "out of binary heap slots");
160 : #endif
161 : }
162 1882573 : heap->bh_nodes[heap->bh_size] = d;
163 1882573 : heap->bh_size++;
164 1882573 : sift_up(heap, heap->bh_size - 1);
165 1882573 : }
166 :
167 : /*
168 : * binaryheap_first
169 : *
170 : * Returns a pointer to the first (root, topmost) node in the heap
171 : * without modifying the heap. The caller must ensure that this
172 : * routine is not used on an empty heap. Always O(1).
173 : */
174 : bh_node_type
175 1079134 : binaryheap_first(binaryheap *heap)
176 : {
177 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
178 1079134 : return heap->bh_nodes[0];
179 : }
180 :
181 : /*
182 : * binaryheap_remove_first
183 : *
184 : * Removes the first (root, topmost) node in the heap and returns a
185 : * pointer to it after rebalancing the heap. The caller must ensure
186 : * that this routine is not used on an empty heap. O(log n) worst
187 : * case.
188 : */
189 : bh_node_type
190 1916410 : binaryheap_remove_first(binaryheap *heap)
191 : {
192 : bh_node_type result;
193 :
194 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
195 :
196 : /* extract the root node, which will be the result */
197 1916410 : result = heap->bh_nodes[0];
198 :
199 : /* easy if heap contains one element */
200 1916410 : if (heap->bh_size == 1)
201 : {
202 6408 : heap->bh_size--;
203 6408 : return result;
204 : }
205 :
206 : /*
207 : * Remove the last node, placing it in the vacated root entry, and sift
208 : * the new root node down to its correct position.
209 : */
210 1910002 : heap->bh_nodes[0] = heap->bh_nodes[--heap->bh_size];
211 1910002 : sift_down(heap, 0);
212 :
213 1910002 : return result;
214 : }
215 :
216 : /*
217 : * binaryheap_remove_node
218 : *
219 : * Removes the nth (zero based) node from the heap. The caller must ensure
220 : * that there are at least (n + 1) nodes in the heap. O(log n) worst case.
221 : */
222 : void
223 91 : binaryheap_remove_node(binaryheap *heap, int n)
224 : {
225 : int cmp;
226 :
227 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
228 : Assert(n >= 0 && n < heap->bh_size);
229 :
230 : /* compare last node to the one that is being removed */
231 91 : cmp = heap->bh_compare(heap->bh_nodes[--heap->bh_size],
232 : heap->bh_nodes[n],
233 : heap->bh_arg);
234 :
235 : /* remove the last node, placing it in the vacated entry */
236 91 : heap->bh_nodes[n] = heap->bh_nodes[heap->bh_size];
237 :
238 : /* sift as needed to preserve the heap property */
239 91 : if (cmp > 0)
240 12 : sift_up(heap, n);
241 79 : else if (cmp < 0)
242 67 : sift_down(heap, n);
243 91 : }
244 :
245 : /*
246 : * binaryheap_replace_first
247 : *
248 : * Replace the topmost element of a non-empty heap, preserving the heap
249 : * property. O(1) in the best case, or O(log n) if it must fall back to
250 : * sifting the new node down.
251 : */
252 : void
253 865268 : binaryheap_replace_first(binaryheap *heap, bh_node_type d)
254 : {
255 : Assert(!binaryheap_empty(heap) && heap->bh_has_heap_property);
256 :
257 865268 : heap->bh_nodes[0] = d;
258 :
259 865268 : if (heap->bh_size > 1)
260 365700 : sift_down(heap, 0);
261 865268 : }
262 :
263 : /*
264 : * Sift a node up to the highest position it can hold according to the
265 : * comparator.
266 : */
267 : static void
268 1882585 : sift_up(binaryheap *heap, int node_off)
269 : {
270 1882585 : bh_node_type node_val = heap->bh_nodes[node_off];
271 :
272 : /*
273 : * Within the loop, the node_off'th array entry is a "hole" that
274 : * notionally holds node_val, but we don't actually store node_val there
275 : * till the end, saving some unnecessary data copying steps.
276 : */
277 5042126 : while (node_off != 0)
278 : {
279 : int cmp;
280 : int parent_off;
281 : bh_node_type parent_val;
282 :
283 : /*
284 : * If this node is smaller than its parent, the heap condition is
285 : * satisfied, and we're done.
286 : */
287 4859158 : parent_off = parent_offset(node_off);
288 4859158 : parent_val = heap->bh_nodes[parent_off];
289 4859158 : cmp = heap->bh_compare(node_val,
290 : parent_val,
291 : heap->bh_arg);
292 4859158 : if (cmp <= 0)
293 1699617 : break;
294 :
295 : /*
296 : * Otherwise, swap the parent value with the hole, and go on to check
297 : * the node's new parent.
298 : */
299 3159541 : heap->bh_nodes[node_off] = parent_val;
300 3159541 : node_off = parent_off;
301 : }
302 : /* Re-fill the hole */
303 1882585 : heap->bh_nodes[node_off] = node_val;
304 1882585 : }
305 :
306 : /*
307 : * Sift a node down from its current position to satisfy the heap
308 : * property.
309 : */
310 : static void
311 2296347 : sift_down(binaryheap *heap, int node_off)
312 : {
313 2296347 : bh_node_type node_val = heap->bh_nodes[node_off];
314 :
315 : /*
316 : * Within the loop, the node_off'th array entry is a "hole" that
317 : * notionally holds node_val, but we don't actually store node_val there
318 : * till the end, saving some unnecessary data copying steps.
319 : */
320 : while (true)
321 16932231 : {
322 19228578 : int left_off = left_offset(node_off);
323 19228578 : int right_off = right_offset(node_off);
324 19228578 : int swap_off = left_off;
325 :
326 : /* Is the right child larger than the left child? */
327 36555022 : if (right_off < heap->bh_size &&
328 17326444 : heap->bh_compare(heap->bh_nodes[left_off],
329 : heap->bh_nodes[right_off],
330 : heap->bh_arg) < 0)
331 8483651 : swap_off = right_off;
332 :
333 : /*
334 : * If no children or parent is >= the larger child, heap condition is
335 : * satisfied, and we're done.
336 : */
337 36996216 : if (left_off >= heap->bh_size ||
338 17767638 : heap->bh_compare(node_val,
339 : heap->bh_nodes[swap_off],
340 : heap->bh_arg) >= 0)
341 : break;
342 :
343 : /*
344 : * Otherwise, swap the hole with the child that violates the heap
345 : * property; then go on to check its children.
346 : */
347 16932231 : heap->bh_nodes[node_off] = heap->bh_nodes[swap_off];
348 16932231 : node_off = swap_off;
349 : }
350 : /* Re-fill the hole */
351 2296347 : heap->bh_nodes[node_off] = node_val;
352 2296347 : }
|
