Line data Source code
1 : //------------------------------------------------------------------------------
2 : // LG_heap: a Heap data structure and its operations
3 : //------------------------------------------------------------------------------
4 :
5 : // LAGraph, (c) 2019-2022 by The LAGraph Contributors, All Rights Reserved.
6 : // SPDX-License-Identifier: BSD-2-Clause
7 : //
8 : // For additional details (including references to third party source code and
9 : // other files) see the LICENSE file or contact permission@sei.cmu.edu. See
10 : // Contributors.txt for a full list of contributors. Created, in part, with
11 : // funding and support from the U.S. Government (see Acknowledgments.txt file).
12 : // DM22-0790
13 :
14 : // Contributed by Timothy A. Davis, Texas A&M University
15 :
16 : //------------------------------------------------------------------------------
17 :
18 : // The Heap is an array of LG_Elements: Heap [1..nheap]. Each entry in the
19 : // Heap is a LG_Element, with a key and name. LG_Element must be defined
20 : // by the including file. For example:
21 :
22 : /*
23 : typedef int64_t LG_key_t ;
24 : typedef struct
25 : {
26 : int64_t name ;
27 : LG_key_t key ;
28 : }
29 : LG_Element ;
30 : #include "LG_heap.h"
31 : */
32 :
33 : #ifndef LG_HEAP_H
34 : #define LG_HEAP_H
35 :
36 : #undef LG_FREE_ALL
37 : #define LG_FREE_ALL ;
38 :
39 : // These methods assume the caller allocates all memory, so no brutal memory
40 : // test is needed.
41 :
42 : //------------------------------------------------------------------------------
43 : // LG_iheap_check: make sure Iheap is correct
44 : //------------------------------------------------------------------------------
45 :
46 : // Ensure that e == Heap [p] implies p == Iheap [e.name] for all entries
47 : // in the heap. Also ensure that e.name is in the range 0:n-1.
48 :
49 10200 : static inline int LG_iheap_check
50 : (
51 : // input:
52 : const LG_Element *restrict Heap, // Heap [1..nheap], not modified
53 : const int64_t *restrict Iheap, // Iheap [0..n-1], not modified
54 : const int64_t n, // element names are in range 0:n-1
55 : const int64_t nheap // the number of nodes in the Heap
56 : )
57 : {
58 :
59 10200 : char *msg = NULL ;
60 10200 : LG_ASSERT_MSG (Heap != NULL && Iheap != NULL && nheap >= 0 && n >= 0, -2000,
61 : "Heap is invalid") ;
62 :
63 : // check all entries in the heap
64 225824 : for (int64_t p = 1 ; p <= nheap ; p++)
65 : {
66 215624 : LG_Element e = Heap [p] ;
67 215624 : int64_t name = e.name ;
68 215624 : LG_ASSERT_MSG (name >= 0 && name < n && p == Iheap [name], -2000,
69 : "Heap is invalid") ;
70 : }
71 :
72 : // check all objects
73 383307 : for (int64_t name = 0 ; name < n ; name++)
74 : {
75 373107 : int64_t p = Iheap [name] ;
76 373107 : if (p <= 0)
77 : {
78 : // object with this name is not in the heap
79 : }
80 : else
81 : {
82 215624 : LG_ASSERT_MSG (p <= nheap, -2000, "position of object is invalid") ;
83 : // object with this name is in the heap at position p
84 215624 : LG_Element e = Heap [p] ;
85 215624 : LG_ASSERT_MSG (e.name == name, -2000, "Heap is invalid") ;
86 : }
87 : }
88 :
89 : // Heap and Iheap are consistent
90 10200 : return (GrB_SUCCESS) ;
91 : }
92 :
93 : //------------------------------------------------------------------------------
94 : // LG_heap_check: make sure the min-heap property holds for the whole Heap
95 : //------------------------------------------------------------------------------
96 :
97 : // Check the entire Heap to see if it has the min-heap property: for all nodes
98 : // in the Heap, the key of a node must less than or equal to the keys of its
99 : // children (duplicate keys may appear). An empty Heap or a Heap of size 1
100 : // always satisfies the min-heap property, but nheap < 0 is invalid. This
101 : // function is for assertions only.
102 :
103 10200 : static inline int LG_heap_check
104 : (
105 : // input:
106 : const LG_Element *restrict Heap, // Heap [1..nheap], not modified
107 : const int64_t *restrict Iheap, // Iheap [0..n-1], not modified
108 : const int64_t n, // element names are in range 0:n-1
109 : const int64_t nheap // the number of nodes in the Heap
110 : )
111 : {
112 :
113 10200 : char *msg = NULL ;
114 10200 : LG_ASSERT_MSG (Heap != NULL && Iheap != NULL && nheap >= 0 && n >= 0, -2000,
115 : "Heap is invalid") ;
116 :
117 : #if 0
118 : // dump the heap
119 : for (int64_t p = 1 ; p <= nheap ; p++)
120 : {
121 : printf ("Heap [%ld]: key %ld name: %ld\n", p, Heap [p].key,
122 : Heap [p].name) ;
123 : int64_t pleft = 2*p ; // left child of node p
124 : int64_t pright = pleft + 1 ; // right child of node p
125 : if (pleft <= nheap)
126 : {
127 : printf (" left child: %ld (key %ld, name %ld)\n",
128 : pleft, Heap [pleft].key, Heap [pleft].name) ;
129 : }
130 : if (pright <= nheap)
131 : {
132 : printf (" right child: %ld (key %ld, name %ld)\n",
133 : pright, Heap [pright].key, Heap [pright].name) ;
134 : }
135 : printf ("\n") ;
136 : }
137 : #endif
138 :
139 : // nodes nheap/2 ... nheap have no children, so no need to check them
140 115535 : for (int64_t p = 1 ; p <= nheap / 2 ; p++)
141 : {
142 :
143 : // consider node p. Its key must be <= the key of both its children.
144 :
145 105335 : int64_t pleft = 2*p ; // left child of node p
146 105335 : int64_t pright = pleft + 1 ; // right child of node p
147 :
148 105335 : LG_ASSERT_MSG (! (pleft <= nheap && Heap [p].key > Heap [pleft].key),
149 : -2000, "the min-heap property is not satisfied") ;
150 :
151 105335 : LG_ASSERT_MSG (! (pright <= nheap && Heap [p].key > Heap [pright].key),
152 : -2000, "the min-heap property is not satisfied") ;
153 : }
154 :
155 : // Heap satisfies the min-heap property; also check Iheap
156 10200 : return (LG_iheap_check (Heap, Iheap, n, nheap)) ;
157 : }
158 :
159 : //------------------------------------------------------------------------------
160 : // LG_heapify: enforce the min-heap property of a node
161 : //------------------------------------------------------------------------------
162 :
163 : // Heapify starting at node p in the Heap. On input, the Heap rooted at node p
164 : // satisfies the min-heap property, except for Heap [p] itself. On output, all
165 : // of the Heap rooted at node p satisfies the min-heap property.
166 :
167 44092 : static inline void LG_heapify
168 : (
169 : int64_t p, // node that needs to be heapified
170 : LG_Element *restrict Heap, // Heap [1..nheap]
171 : int64_t *restrict Iheap, // Iheap [0..n-1]
172 : const int64_t n, // max element name
173 : const int64_t nheap // the number of nodes in the Heap
174 : )
175 : {
176 :
177 : //--------------------------------------------------------------------------
178 : // check inputs and check for quick return
179 : //--------------------------------------------------------------------------
180 :
181 : ASSERT (Heap != NULL && Iheap != NULL) ;
182 :
183 44092 : if (p > nheap / 2 || nheap <= 1)
184 : {
185 : // nothing to do. p has no children in the Heap.
186 : // Also safely do nothing if p is outside the Heap (p > nheap).
187 622 : return ;
188 : }
189 :
190 : //--------------------------------------------------------------------------
191 : // get the element to heapify
192 : //--------------------------------------------------------------------------
193 :
194 : // Get the element e at node p in the Heap; the one that needs heapifying.
195 43470 : LG_Element e = Heap [p] ;
196 :
197 : // There is now a "hole" at Heap [p], with no element in it.
198 :
199 : //--------------------------------------------------------------------------
200 : // heapify
201 : //--------------------------------------------------------------------------
202 :
203 : while (true)
204 233225 : {
205 :
206 : //----------------------------------------------------------------------
207 : // consider node p in the Heap
208 : //----------------------------------------------------------------------
209 :
210 : // Heap [p] is the "hole" in the Heap
211 :
212 276695 : int64_t pleft = 2*p ; // left child of node p
213 276695 : int64_t pright = pleft + 1 ; // right child of node p
214 :
215 276695 : if (pright <= nheap)
216 : {
217 :
218 : //------------------------------------------------------------------
219 : // both left and right children are in the Heap
220 : //------------------------------------------------------------------
221 :
222 267934 : LG_Element eleft = Heap [pleft] ;
223 267934 : LG_Element eright = Heap [pright] ;
224 267934 : if (eleft.key < eright.key)
225 : {
226 : // left node has a smaller key than the right node
227 119095 : if (e.key > eleft.key)
228 : {
229 : // key of element e is bigger than the left child of p, so
230 : // bubble up the left child into the hole at Heap [p] and
231 : // continue down the left child. The hole moves to node
232 : // pleft.
233 118616 : Heap [p] = eleft ;
234 118616 : Iheap [eleft.name] = p ;
235 118616 : p = pleft ;
236 : }
237 : else
238 : {
239 : // done! key of element e is is smaller than the left
240 : // child of p; place e in the hole at p, and we're done.
241 479 : Heap [p] = e ;
242 479 : Iheap [e.name] = p ;
243 34709 : return ;
244 : }
245 : }
246 : else
247 : {
248 : // right node has a smaller key than the left node
249 148839 : if (e.key > eright.key)
250 : {
251 : // key of element e is bigger than the right child of p, so
252 : // bubble up the right child into hole at Heap [p] and
253 : // continue down the right child. The hole moves to node
254 : // pright.
255 114609 : Heap [p] = eright ;
256 114609 : Iheap [eright.name] = p ;
257 114609 : p = pright ;
258 : }
259 : else
260 : {
261 : // done! key of element e is is smaller than the right
262 : // child of p; place e in the hole at p, and we're done.
263 34230 : Heap [p] = e ;
264 34230 : Iheap [e.name] = p ;
265 34230 : return ;
266 : }
267 : }
268 : }
269 : else
270 : {
271 :
272 : //------------------------------------------------------------------
273 : // right child is not in the Heap, see if left child is in the Heap
274 : //------------------------------------------------------------------
275 :
276 8761 : if (pleft <= nheap)
277 : {
278 : // left child is in the Heap; check its key
279 1185 : LG_Element eleft = Heap [pleft] ;
280 1185 : if (e.key > eleft.key)
281 : {
282 : // key of element e is bigger than the left child of p, so
283 : // bubble up the left child into the hole at Heap [p] and
284 : // continue down the left child. The hole moves to node
285 : // pleft.
286 289 : Heap [p] = eleft ;
287 289 : Iheap [eleft.name] = p ;
288 289 : p = pleft ;
289 : }
290 : }
291 :
292 : //------------------------------------------------------------------
293 : // node p is a hole, and it has no children
294 : //------------------------------------------------------------------
295 :
296 : // put e in the hole, and we're done
297 8761 : Heap [p] = e ;
298 8761 : Iheap [e.name] = p ;
299 8761 : return ;
300 : }
301 : }
302 : }
303 :
304 : //------------------------------------------------------------------------------
305 : // LG_heap_build: construct a Heap
306 : //------------------------------------------------------------------------------
307 :
308 : // On input, the Heap [1..nheap] may not satisfy the min-heap property, but
309 : // Iheap must already be initialized.
310 : // If e = Heap [p], then Iheap [e.name] = p must hold.
311 :
312 : // On output, the elements have been rearranged so that it satisfies the
313 : // heap property.
314 :
315 : static inline void LG_heap_build
316 : (
317 : LG_Element *restrict Heap, // Heap [1..nheap]
318 : int64_t *restrict Iheap, // Iheap [0..n-1]
319 : const int64_t n, // max element name
320 : const int64_t nheap // the number of nodes in the Heap
321 : )
322 : {
323 :
324 : //--------------------------------------------------------------------------
325 : // check inputs
326 : //--------------------------------------------------------------------------
327 :
328 : ASSERT (Heap != NULL && nheap >= 0) ;
329 : ASSERT (LG_iheap_check (Heap, Iheap, n, nheap)) ;
330 :
331 : //--------------------------------------------------------------------------
332 : // build the Heap
333 : //--------------------------------------------------------------------------
334 :
335 : for (int64_t p = nheap / 2 ; p >= 1 ; p--)
336 : {
337 : LG_heapify (p, Heap, Iheap, n, nheap) ;
338 : }
339 :
340 : //--------------------------------------------------------------------------
341 : // check result
342 : //--------------------------------------------------------------------------
343 :
344 : // Heap [1..nheap] now satisfies the min-heap property
345 : ASSERT (LG_heap_check (Heap, Iheap, n, nheap)) ;
346 : }
347 :
348 : //------------------------------------------------------------------------------
349 : // LG_heap_delete: delete an element in the middle of a Heap
350 : //------------------------------------------------------------------------------
351 :
352 44092 : static inline void LG_heap_delete
353 : (
354 : int64_t p, // node that needs to be deleted
355 : LG_Element *restrict Heap, // Heap [1..nheap]
356 : int64_t *restrict Iheap, // Iheap [0..n-1]
357 : const int64_t n, // max element name
358 : int64_t *restrict nheap // the number of nodes in the Heap;
359 : // decremented on output
360 : )
361 : {
362 :
363 : //--------------------------------------------------------------------------
364 : // check inputs
365 : //--------------------------------------------------------------------------
366 :
367 : ASSERT (Heap != NULL && Iheap != NULL && (*nheap) >= 0) ;
368 : ASSERT (p >= 1 && p <= (*nheap)) ;
369 :
370 : //--------------------------------------------------------------------------
371 : // delete node p from the Heap
372 : //--------------------------------------------------------------------------
373 :
374 : // move the last node to node p and decrement the # of nodes in the Heap
375 44092 : LG_Element elast = Heap [*nheap] ; // last node in the heap
376 44092 : LG_Element edel = Heap [p] ; // element to delete from the heap
377 44092 : Heap [p] = elast ; // move last node in the heap to position p
378 44092 : Iheap [elast.name] = p ; // elast has been moved to position p
379 44092 : Iheap [edel.name] = 0 ; // edel is no longer in the heap
380 44092 : (*nheap)-- ; // one less entry in the heap
381 :
382 : // heapify node p (safely does nothing if node p was the one just deleted)
383 44092 : LG_heapify (p, Heap, Iheap, n, (*nheap)) ;
384 44092 : }
385 :
386 : //------------------------------------------------------------------------------
387 : // LG_heap_decrease_key: decrease the key of an entry in the heap
388 : //------------------------------------------------------------------------------
389 :
390 60199 : static inline void LG_heap_decrease_key
391 : (
392 : int64_t p, // entry to modify in the heap
393 : const LG_key_t new_key, // new key value of Heap [p]
394 : LG_Element *restrict Heap, // Heap [1..nheap]
395 : int64_t *restrict Iheap, // Iheap [0..n-1]
396 : const int64_t n, // max element name
397 : const int64_t nheap // the number of nodes in the Heap
398 : )
399 : {
400 : ASSERT (Heap != NULL && Iheap != NULL) ;
401 : ASSERT (p >= 1 && p < nheap) ;
402 : ASSERT (new_key < Heap [p].key) ;
403 :
404 : // printf ("Decreasing Heap [%ld] = name: %ld key: from %ld to %ld\n",
405 : // p, Heap [p].name, Heap [p].key, new_key) ;
406 :
407 60199 : Heap [p].key = new_key ;
408 60199 : int64_t parent = p/2 ;
409 :
410 187582 : while (p > 1 && Heap [parent].key > Heap [p].key)
411 : {
412 : // swap Heap [p] and Heap [parent]
413 : // printf ("swap positions %ld and %ld\n", p, parent) ;
414 :
415 127383 : LG_Element e = Heap [p] ;
416 127383 : Heap [p] = Heap [parent] ;
417 127383 : Heap [parent] = e ;
418 :
419 : // update the inverse heap
420 127383 : Iheap [Heap [p].name] = p ;
421 127383 : Iheap [Heap [parent].name] = parent ;
422 :
423 : // advance up to the parent
424 127383 : p = parent ;
425 127383 : parent = p/2 ;
426 : }
427 60199 : }
428 :
429 : #endif
|
