Line data Source code
1 : /*-------------------------------------------------------------------------
2 : *
3 : * pairingheap.c
4 : * A Pairing Heap implementation
5 : *
6 : * A pairing heap is a data structure that's useful for implementing
7 : * priority queues. It is simple to implement, and provides amortized O(1)
8 : * insert and find-min operations, and amortized O(log n) delete-min.
9 : *
10 : * The pairing heap was first described in this paper:
11 : *
12 : * Michael L. Fredman, Robert Sedgewick, Daniel D. Sleator, and Robert E.
13 : * Tarjan. 1986.
14 : * The pairing heap: a new form of self-adjusting heap.
15 : * Algorithmica 1, 1 (January 1986), pages 111-129. DOI: 10.1007/BF01840439
16 : *
17 : * Portions Copyright (c) 2012-2025, PostgreSQL Global Development Group
18 : *
19 : * IDENTIFICATION
20 : * src/backend/lib/pairingheap.c
21 : *
22 : *-------------------------------------------------------------------------
23 : */
24 :
25 : #include "postgres.h"
26 :
27 : #include "lib/pairingheap.h"
28 :
29 : static pairingheap_node *merge(pairingheap *heap, pairingheap_node *a,
30 : pairingheap_node *b);
31 : static pairingheap_node *merge_children(pairingheap *heap,
32 : pairingheap_node *children);
33 :
34 : /*
35 : * pairingheap_allocate
36 : *
37 : * Returns a pointer to a newly-allocated heap, with the heap property defined
38 : * by the given comparator function, which will be invoked with the additional
39 : * argument specified by 'arg'.
40 : */
41 : pairingheap *
42 9180 : pairingheap_allocate(pairingheap_comparator compare, void *arg)
43 : {
44 : pairingheap *heap;
45 :
46 9180 : heap = (pairingheap *) palloc(sizeof(pairingheap));
47 9180 : pairingheap_initialize(heap, compare, arg);
48 :
49 9180 : return heap;
50 : }
51 :
52 : /*
53 : * pairingheap_initialize
54 : *
55 : * Same as pairingheap_allocate(), but initializes the pairing heap in-place
56 : * rather than allocating a new chunk of memory. Useful to store the pairing
57 : * heap in a shared memory.
58 : */
59 : void
60 13576 : pairingheap_initialize(pairingheap *heap, pairingheap_comparator compare,
61 : void *arg)
62 : {
63 13576 : heap->ph_compare = compare;
64 13576 : heap->ph_arg = arg;
65 :
66 13576 : heap->ph_root = NULL;
67 13576 : }
68 :
69 : /*
70 : * pairingheap_free
71 : *
72 : * Releases memory used by the given pairingheap.
73 : *
74 : * Note: The nodes in the heap are not freed!
75 : */
76 : void
77 0 : pairingheap_free(pairingheap *heap)
78 : {
79 0 : pfree(heap);
80 0 : }
81 :
82 : /*
83 : * A helper function to merge two subheaps into one.
84 : *
85 : * The subheap with smaller value is put as a child of the other one (assuming
86 : * a max-heap).
87 : *
88 : * The next_sibling and prev_or_parent pointers of the input nodes are
89 : * ignored. On return, the returned node's next_sibling and prev_or_parent
90 : * pointers are garbage.
91 : */
92 : static pairingheap_node *
93 26636878 : merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
94 : {
95 26636878 : if (a == NULL)
96 5519346 : return b;
97 21117532 : if (b == NULL)
98 0 : return a;
99 :
100 : /* swap 'a' and 'b' so that 'a' is the one with larger value */
101 21117532 : if (heap->ph_compare(a, b, heap->ph_arg) < 0)
102 : {
103 : pairingheap_node *tmp;
104 :
105 2080484 : tmp = a;
106 2080484 : a = b;
107 2080484 : b = tmp;
108 : }
109 :
110 : /* and put 'b' as a child of 'a' */
111 21117532 : if (a->first_child)
112 7844376 : a->first_child->prev_or_parent = b;
113 21117532 : b->prev_or_parent = a;
114 21117532 : b->next_sibling = a->first_child;
115 21117532 : a->first_child = b;
116 :
117 21117532 : return a;
118 : }
119 :
120 : /*
121 : * pairingheap_add
122 : *
123 : * Adds the given node to the heap in O(1) time.
124 : */
125 : void
126 22421938 : pairingheap_add(pairingheap *heap, pairingheap_node *node)
127 : {
128 22421938 : node->first_child = NULL;
129 :
130 : /* Link the new node as a new tree */
131 22421938 : heap->ph_root = merge(heap, heap->ph_root, node);
132 22421938 : heap->ph_root->prev_or_parent = NULL;
133 22421938 : heap->ph_root->next_sibling = NULL;
134 22421938 : }
135 :
136 : /*
137 : * pairingheap_first
138 : *
139 : * Returns a pointer to the first (root, topmost) node in the heap without
140 : * modifying the heap. The caller must ensure that this routine is not used on
141 : * an empty heap. Always O(1).
142 : */
143 : pairingheap_node *
144 3905602 : pairingheap_first(pairingheap *heap)
145 : {
146 : Assert(!pairingheap_is_empty(heap));
147 :
148 3905602 : return heap->ph_root;
149 : }
150 :
151 : /*
152 : * pairingheap_remove_first
153 : *
154 : * Removes the first (root, topmost) node in the heap and returns a pointer to
155 : * it after rebalancing the heap. The caller must ensure that this routine is
156 : * not used on an empty heap. O(log n) amortized.
157 : */
158 : pairingheap_node *
159 6895566 : pairingheap_remove_first(pairingheap *heap)
160 : {
161 : pairingheap_node *result;
162 : pairingheap_node *children;
163 :
164 : Assert(!pairingheap_is_empty(heap));
165 :
166 : /* Remove the root, and form a new heap of its children. */
167 6895566 : result = heap->ph_root;
168 6895566 : children = result->first_child;
169 :
170 6895566 : heap->ph_root = merge_children(heap, children);
171 6895566 : if (heap->ph_root)
172 : {
173 1376528 : heap->ph_root->prev_or_parent = NULL;
174 1376528 : heap->ph_root->next_sibling = NULL;
175 : }
176 :
177 6895566 : return result;
178 : }
179 :
180 : /*
181 : * Remove 'node' from the heap. O(log n) amortized.
182 : */
183 : void
184 21852188 : pairingheap_remove(pairingheap *heap, pairingheap_node *node)
185 : {
186 : pairingheap_node *children;
187 : pairingheap_node *replacement;
188 : pairingheap_node *next_sibling;
189 : pairingheap_node **prev_ptr;
190 :
191 : /*
192 : * If the removed node happens to be the root node, do it with
193 : * pairingheap_remove_first().
194 : */
195 21852188 : if (node == heap->ph_root)
196 : {
197 6359058 : (void) pairingheap_remove_first(heap);
198 6359058 : return;
199 : }
200 :
201 : /*
202 : * Before we modify anything, remember the removed node's first_child and
203 : * next_sibling pointers.
204 : */
205 15493130 : children = node->first_child;
206 15493130 : next_sibling = node->next_sibling;
207 :
208 : /*
209 : * Also find the pointer to the removed node in its previous sibling, or
210 : * if this is the first child of its parent, in its parent.
211 : */
212 15493130 : if (node->prev_or_parent->first_child == node)
213 15467844 : prev_ptr = &node->prev_or_parent->first_child;
214 : else
215 25286 : prev_ptr = &node->prev_or_parent->next_sibling;
216 : Assert(*prev_ptr == node);
217 :
218 : /*
219 : * If this node has children, make a new subheap of the children and link
220 : * the subheap in place of the removed node. Otherwise just unlink this
221 : * node.
222 : */
223 15493130 : if (children)
224 : {
225 2386 : replacement = merge_children(heap, children);
226 :
227 2386 : replacement->prev_or_parent = node->prev_or_parent;
228 2386 : replacement->next_sibling = node->next_sibling;
229 2386 : *prev_ptr = replacement;
230 2386 : if (next_sibling)
231 2192 : next_sibling->prev_or_parent = replacement;
232 : }
233 : else
234 : {
235 15490744 : *prev_ptr = next_sibling;
236 15490744 : if (next_sibling)
237 3591812 : next_sibling->prev_or_parent = node->prev_or_parent;
238 : }
239 : }
240 :
241 : /*
242 : * Merge a list of subheaps into a single heap.
243 : *
244 : * This implements the basic two-pass merging strategy, first forming pairs
245 : * from left to right, and then merging the pairs.
246 : */
247 : static pairingheap_node *
248 6897952 : merge_children(pairingheap *heap, pairingheap_node *children)
249 : {
250 : pairingheap_node *curr,
251 : *next;
252 : pairingheap_node *pairs;
253 : pairingheap_node *newroot;
254 :
255 6897952 : if (children == NULL || children->next_sibling == NULL)
256 6391490 : return children;
257 :
258 : /* Walk the subheaps from left to right, merging in pairs */
259 506462 : next = children;
260 506462 : pairs = NULL;
261 : for (;;)
262 : {
263 2745738 : curr = next;
264 :
265 2745738 : if (curr == NULL)
266 263612 : break;
267 :
268 2482126 : if (curr->next_sibling == NULL)
269 : {
270 : /* last odd node at the end of list */
271 242850 : curr->next_sibling = pairs;
272 242850 : pairs = curr;
273 242850 : break;
274 : }
275 :
276 2239276 : next = curr->next_sibling->next_sibling;
277 :
278 : /* merge this and the next subheap, and add to 'pairs' list. */
279 :
280 2239276 : curr = merge(heap, curr, curr->next_sibling);
281 2239276 : curr->next_sibling = pairs;
282 2239276 : pairs = curr;
283 : }
284 :
285 : /*
286 : * Merge all the pairs together to form a single heap.
287 : */
288 506462 : newroot = pairs;
289 506462 : next = pairs->next_sibling;
290 2482126 : while (next)
291 : {
292 1975664 : curr = next;
293 1975664 : next = curr->next_sibling;
294 :
295 1975664 : newroot = merge(heap, newroot, curr);
296 : }
297 :
298 506462 : return newroot;
299 : }
300 :
301 : /*
302 : * A debug function to dump the contents of the heap as a string.
303 : *
304 : * The 'dumpfunc' callback appends a string representation of a single node
305 : * to the StringInfo. 'opaque' can be used to pass more information to the
306 : * callback.
307 : */
308 : #ifdef PAIRINGHEAP_DEBUG
309 : static void
310 : pairingheap_dump_recurse(StringInfo buf,
311 : pairingheap_node *node,
312 : void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
313 : void *opaque,
314 : int depth,
315 : pairingheap_node *prev_or_parent)
316 : {
317 : while (node)
318 : {
319 : Assert(node->prev_or_parent == prev_or_parent);
320 :
321 : appendStringInfoSpaces(buf, depth * 4);
322 : dumpfunc(node, buf, opaque);
323 : appendStringInfoChar(buf, '\n');
324 : if (node->first_child)
325 : pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
326 : prev_or_parent = node;
327 : node = node->next_sibling;
328 : }
329 : }
330 :
331 : char *
332 : pairingheap_dump(pairingheap *heap,
333 : void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
334 : void *opaque)
335 : {
336 : StringInfoData buf;
337 :
338 : if (!heap->ph_root)
339 : return pstrdup("(empty)");
340 :
341 : initStringInfo(&buf);
342 :
343 : pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
344 :
345 : return buf.data;
346 : }
347 : #endif
|
