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-2019, 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
29static pairingheap_node *merge(pairingheap *heap, pairingheap_node *a,
30 pairingheap_node *b);
31static 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 */
41pairingheap *
42pairingheap_allocate(pairingheap_comparator compare, void *arg)
43{
44 pairingheap *heap;
45
46 heap = (pairingheap *) palloc(sizeof(pairingheap));
47 heap->ph_compare = compare;
48 heap->ph_arg = arg;
49
50 heap->ph_root = NULL;
51
52 return heap;
53}
54
55/*
56 * pairingheap_free
57 *
58 * Releases memory used by the given pairingheap.
59 *
60 * Note: The nodes in the heap are not freed!
61 */
62void
63pairingheap_free(pairingheap *heap)
64{
65 pfree(heap);
66}
67
68/*
69 * A helper function to merge two subheaps into one.
70 *
71 * The subheap with smaller value is put as a child of the other one (assuming
72 * a max-heap).
73 *
74 * The next_sibling and prev_or_parent pointers of the input nodes are
75 * ignored. On return, the returned node's next_sibling and prev_or_parent
76 * pointers are garbage.
77 */
78static pairingheap_node *
79merge(pairingheap *heap, pairingheap_node *a, pairingheap_node *b)
80{
81 if (a == NULL)
82 return b;
83 if (b == NULL)
84 return a;
85
86 /* swap 'a' and 'b' so that 'a' is the one with larger value */
87 if (heap->ph_compare(a, b, heap->ph_arg) < 0)
88 {
89 pairingheap_node *tmp;
90
91 tmp = a;
92 a = b;
93 b = tmp;
94 }
95
96 /* and put 'b' as a child of 'a' */
97 if (a->first_child)
98 a->first_child->prev_or_parent = b;
99 b->prev_or_parent = a;
100 b->next_sibling = a->first_child;
101 a->first_child = b;
102
103 return a;
104}
105
106/*
107 * pairingheap_add
108 *
109 * Adds the given node to the heap in O(1) time.
110 */
111void
112pairingheap_add(pairingheap *heap, pairingheap_node *node)
113{
114 node->first_child = NULL;
115
116 /* Link the new node as a new tree */
117 heap->ph_root = merge(heap, heap->ph_root, node);
118 heap->ph_root->prev_or_parent = NULL;
119 heap->ph_root->next_sibling = NULL;
120}
121
122/*
123 * pairingheap_first
124 *
125 * Returns a pointer to the first (root, topmost) node in the heap without
126 * modifying the heap. The caller must ensure that this routine is not used on
127 * an empty heap. Always O(1).
128 */
129pairingheap_node *
130pairingheap_first(pairingheap *heap)
131{
132 Assert(!pairingheap_is_empty(heap));
133
134 return heap->ph_root;
135}
136
137/*
138 * pairingheap_remove_first
139 *
140 * Removes the first (root, topmost) node in the heap and returns a pointer to
141 * it after rebalancing the heap. The caller must ensure that this routine is
142 * not used on an empty heap. O(log n) amortized.
143 */
144pairingheap_node *
145pairingheap_remove_first(pairingheap *heap)
146{
147 pairingheap_node *result;
148 pairingheap_node *children;
149
150 Assert(!pairingheap_is_empty(heap));
151
152 /* Remove the root, and form a new heap of its children. */
153 result = heap->ph_root;
154 children = result->first_child;
155
156 heap->ph_root = merge_children(heap, children);
157 if (heap->ph_root)
158 {
159 heap->ph_root->prev_or_parent = NULL;
160 heap->ph_root->next_sibling = NULL;
161 }
162
163 return result;
164}
165
166/*
167 * Remove 'node' from the heap. O(log n) amortized.
168 */
169void
170pairingheap_remove(pairingheap *heap, pairingheap_node *node)
171{
172 pairingheap_node *children;
173 pairingheap_node *replacement;
174 pairingheap_node *next_sibling;
175 pairingheap_node **prev_ptr;
176
177 /*
178 * If the removed node happens to be the root node, do it with
179 * pairingheap_remove_first().
180 */
181 if (node == heap->ph_root)
182 {
183 (void) pairingheap_remove_first(heap);
184 return;
185 }
186
187 /*
188 * Before we modify anything, remember the removed node's first_child and
189 * next_sibling pointers.
190 */
191 children = node->first_child;
192 next_sibling = node->next_sibling;
193
194 /*
195 * Also find the pointer to the removed node in its previous sibling, or
196 * if this is the first child of its parent, in its parent.
197 */
198 if (node->prev_or_parent->first_child == node)
199 prev_ptr = &node->prev_or_parent->first_child;
200 else
201 prev_ptr = &node->prev_or_parent->next_sibling;
202 Assert(*prev_ptr == node);
203
204 /*
205 * If this node has children, make a new subheap of the children and link
206 * the subheap in place of the removed node. Otherwise just unlink this
207 * node.
208 */
209 if (children)
210 {
211 replacement = merge_children(heap, children);
212
213 replacement->prev_or_parent = node->prev_or_parent;
214 replacement->next_sibling = node->next_sibling;
215 *prev_ptr = replacement;
216 if (next_sibling)
217 next_sibling->prev_or_parent = replacement;
218 }
219 else
220 {
221 *prev_ptr = next_sibling;
222 if (next_sibling)
223 next_sibling->prev_or_parent = node->prev_or_parent;
224 }
225}
226
227/*
228 * Merge a list of subheaps into a single heap.
229 *
230 * This implements the basic two-pass merging strategy, first forming pairs
231 * from left to right, and then merging the pairs.
232 */
233static pairingheap_node *
234merge_children(pairingheap *heap, pairingheap_node *children)
235{
236 pairingheap_node *curr,
237 *next;
238 pairingheap_node *pairs;
239 pairingheap_node *newroot;
240
241 if (children == NULL || children->next_sibling == NULL)
242 return children;
243
244 /* Walk the subheaps from left to right, merging in pairs */
245 next = children;
246 pairs = NULL;
247 for (;;)
248 {
249 curr = next;
250
251 if (curr == NULL)
252 break;
253
254 if (curr->next_sibling == NULL)
255 {
256 /* last odd node at the end of list */
257 curr->next_sibling = pairs;
258 pairs = curr;
259 break;
260 }
261
262 next = curr->next_sibling->next_sibling;
263
264 /* merge this and the next subheap, and add to 'pairs' list. */
265
266 curr = merge(heap, curr, curr->next_sibling);
267 curr->next_sibling = pairs;
268 pairs = curr;
269 }
270
271 /*
272 * Merge all the pairs together to form a single heap.
273 */
274 newroot = pairs;
275 next = pairs->next_sibling;
276 while (next)
277 {
278 curr = next;
279 next = curr->next_sibling;
280
281 newroot = merge(heap, newroot, curr);
282 }
283
284 return newroot;
285}
286
287/*
288 * A debug function to dump the contents of the heap as a string.
289 *
290 * The 'dumpfunc' callback appends a string representation of a single node
291 * to the StringInfo. 'opaque' can be used to pass more information to the
292 * callback.
293 */
294#ifdef PAIRINGHEAP_DEBUG
295static void
296pairingheap_dump_recurse(StringInfo buf,
297 pairingheap_node *node,
298 void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
299 void *opaque,
300 int depth,
301 pairingheap_node *prev_or_parent)
302{
303 while (node)
304 {
305 Assert(node->prev_or_parent == prev_or_parent);
306
307 appendStringInfoSpaces(buf, depth * 4);
308 dumpfunc(node, buf, opaque);
309 appendStringInfoChar(buf, '\n');
310 if (node->first_child)
311 pairingheap_dump_recurse(buf, node->first_child, dumpfunc, opaque, depth + 1, node);
312 prev_or_parent = node;
313 node = node->next_sibling;
314 }
315}
316
317char *
318pairingheap_dump(pairingheap *heap,
319 void (*dumpfunc) (pairingheap_node *node, StringInfo buf, void *opaque),
320 void *opaque)
321{
322 StringInfoData buf;
323
324 if (!heap->ph_root)
325 return pstrdup("(empty)");
326
327 initStringInfo(&buf);
328
329 pairingheap_dump_recurse(&buf, heap->ph_root, dumpfunc, opaque, 0, NULL);
330
331 return buf.data;
332}
333#endif
334