1 /*
2 *
3 * Copyright (c) 2003 The Regents of the University of California. All
4 * rights reserved.
5 *
6 * Redistribution and use in source and binary forms, with or without
7 * modification, are permitted provided that the following conditions
8 * are met:
9 *
10 * - Redistributions of source code must retain the above copyright
11 * notice, this list of conditions and the following disclaimer.
12 *
13 * - Neither the name of the University nor the names of its
14 * contributors may be used to endorse or promote products derived
15 * from this software without specific prior written permission.
16 *
17 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS''
18 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
19 * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
20 * PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR
21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
28 *
29 */
30
31
32 #include <stdlib.h>
33 #include <stdio.h>
34 #include <assert.h>
35 #include <string.h>
36
37 #include "heap.h"
38 #include "libmisc/misc.h"
39
40 /* assumes 'i' is an integral type */
41 #define PARENT(I) ((I) / 2)
42 #define LEFT(I) (2 * (I))
43 #define RIGHT(I) (2 * (I) + 1)
44
45 /* used in the link list when keeping track of which subtree roots we still need
46 * to process when looking for a node with a particular key */
47 struct list_elt
48 {
49 struct list_elt *next;
50 int i; /* index of element in heap array */
51 };
52
53 void heapify(struct heap *h, int i);
54
55 /* take an element in the heap array, check if it satisfies the heap property,
56 * and if it does not propagate it into proper location so that it does. Of
57 * course, the heap is re-arranged in the process to make sure that the rest of
58 * the heap structure is not broken. This does assume (I think) that the rest of
59 * the heap is properly structured
60 *
61 * This function propagates an element "down" (not up). So, only subtree to
62 * which this element belongs will be rearranged
63 *
64 * NOTE: dont forget, i must start from 1. although, this being an internal
65 * routine, it does not really matter since this is supposed to be an
66 * internal routine anyway, and indexing does not get exposed to the
67 * public interface
68 *
69 * 'struct heap *h' - heap we're dealing with
70 * 'int i' - index (in the heap array) of the element we're
71 * "heapifying"
72 */
73 void
74 heapify(struct heap *h, int i)
75 {
76 int left = LEFT(i); /* index of the head of left subtree */
77 int right = RIGHT(i); /* index of the head of right subtree */
78 int index; /* index of ellement we're currently heapifying */
79 int largest; /* temp index of largest of 3 elements:
80 a[LEFT(index)], a[RIGHT(index), a[index] */
81 struct heap_item temp; /* temporary for exchanging values */
82
83 assert(h);
84 assert(h->a);
85 /* i can't be zero, since we assume that we start counting from 1! */
86 assert(i > 0);
87
88 /* throughout our implementation we make sure that size <= length of the
89 * heap, so we won't overrun the bounds here... */
90
91 index = i;
92
93 while(1)
94 {
95 left = LEFT(index);
96 right = RIGHT(index);
97
98 if ((left <= h->size) && (h->a[left].value > h->a[index].value))
99 {
100 largest = left;
101 }
102 else
103 {
104 largest = index;
105 }
106
107 if ((right <= h->size) && (h->a[right].value > h->a[largest].value))
108 {
109 largest = right;
110 }
111
112 /* if element at position 'index' is largest we're done. Otherwise, we
113 * swap the element with the largest of the two roots of subtrees */
114 if (largest != index)
115 {
116 temp = h->a[index];
117 h->a[index] = h->a[largest];
118 h->a[largest] = temp;
119
120 index = largest;
121 }
122 else
123 {
124 break;
125 }
126 }
127 }
128
129 void
130 heap_insert(struct heap *h, unsigned long key, unsigned long value)
131 {
132 int i; /* index of element we're currently propagating through heap */
133
134 assert(h);
135
136 h->size ++;
137
138 /* with addition of this element we will run out of space to store
139 * elements in the heap, so reallocate */
140 if (h->size >= h->length)
141 {
142 /* normally, we'd just double the space, but because the very first time
143 * through the function h->length will be 0, and that would not work */
144 h->length = h->length * 2 + 1;
145 /* we allocate 1 more then 'length' because we start counting at 1, not
146 * at zero! This is clunky, but this way it is closer to the pseudocode
147 * in the book, hence easier to follow... yeah, it has an effect of
148 * "leaking" one element. Not a big deal. */
149 h->a = realloc(h->a, (h->length + 1) * sizeof(* (h->a)));
150 assert(h->a);
151 }
152
153 i = h->size;
154
155 while ((i > 1) && (h->a[PARENT(i)].value < value))
156 {
157 h->a[i] = h->a[PARENT(i)];
158 i = PARENT(i);
159 }
160
161 h->a[i].key = key;
162 h->a[i].value = value;
163 }
164
165 struct heap *
166 heap_alloc(void)
167 {
168 struct heap *h = NULL;
169
170 h = malloc(sizeof(struct heap));
171 assert(h);
172
173 h->length = 0;
174 h->size = 0;
175 h->a = NULL;
176
177 return h;
178 }
179
180 void
181 heap_destroy(struct heap *h)
182 {
183 assert(h);
184
185 free(h->a);
186 free(h);
187 }
188
189 /* eventually maybe make it pretty-print. For now, just dump the array */
190 void
191 heap_print(struct heap *h)
192 {
193 int i;
194
195 assert(h);
196
197 /* dont forget to skip the very first element, which isn't meaningful */
198 for (i = 1; i <= h->size; i ++)
199 {
200 printf("(%lu, %lu) ", h->a[i].key, h->a[i].value);
201 }
202
203 printf("\n");
204 }
205
206 int
207 heap_empty(struct heap *h)
208 {
209 assert(h);
210
211 return (h->size < 1) ? 1 : 0 ;
212 }
213
214 int
215 heap_peek_max(struct heap *h, unsigned long *key, unsigned long *value)
216 {
217 assert(h);
218 assert(key);
219 assert(value);
220
221 if (heap_empty(h))
222 {
223 return -1;
224 }
225
226 /* remember, our heap starts counting at 1! */
227 *key = h->a[1].key;
228 *value = h->a[1].value;
229
230 return 1;
231 }
232
233 void
234 heap_rmv_max(struct heap *h)
235 {
236 assert(h);
237
238 /* ensure the heap isn't empty or anything */
239 if (h->size < 1)
240 {
241 return ;
242 }
243
244 /* overwrite the very first element. Remember, for our heap, the count
245 * starts at 1 */
246 h->a[1] = h->a[h->size];
247 h->size --;
248 heapify(h, 1);
249 }
250
251 int
252 heap_extract_max(struct heap *h, unsigned long *key, unsigned long *data)
253 {
254 /* heap_peek_max() returns negative when encounters an empty heap */
255 if (0 < heap_peek_max(h, key, data))
256 {
257 heap_rmv_max(h);
258 return 1;
259 }
260 else
261 {
262 return -1;
263 }
264 }
265
266 /* if item not found, will return a negative value
267 * (TODO: explain how this works) */
268 static int
269 find_position(struct heap *h, unsigned long key, unsigned long value)
270 {
271 /* pointer to the first element on the list */
272 struct list_elt *first = NULL;
273 /* pointer to the last element on the list */
274 struct list_elt *last = NULL;
275 struct list_elt *cur;
276 struct list_elt *new;
277 /* indeces in the array of heap elements */
278 int left, right;
279 /* index of the element in heap array (negative if not found) */
280 int index = -1;
281
282 assert(h);
283
284 /* before doing anything, make sure our value is smaller then root. Otherwise,
285 * we will not be able to find it (since the heap property would be
286 * violated) */
287 if (value > h->a[1].value)
288 {
289 return -1;
290 }
291 else if ((value == h->a[1].value) && (key == h->a[1].key))
292 {
293 return 1;
294 }
295
296 /* add a root node */
297 assert(first = malloc(sizeof(struct list_elt)));
298 first->i = 1;
299 first->next = NULL;
300 last = first;
301
302 /* process a list of nodes, who's siblings may potentially be the element
303 * we're looking for */
304 while (first)
305 {
306 /* remove the head element. if only one element was present, head was
307 * the same as tail, and both will become NULL when it is removed */
308 cur = first;
309 first = first->next;
310 /* yep, only had one element */
311 if (! first)
312 {
313 last = NULL;
314 }
315
316 /* sibling indeces */
317 left = LEFT(cur->i);
318 right = RIGHT(cur->i);
319
320 /* if the element we're looking for is a left child, return its index */
321 if ( (left <= h->size)
322 && (h->a[left].value == value)
323 && (h->a[left].key == key))
324 {
325 index = left;
326 /* current element has already been unlinked, so free it */
327 free(cur);
328 break;
329 }
330
331 /* if the element we're looking for is a right child,
332 * return its index */
333 if ( (right <= h->size)
334 && (h->a[right].value == value)
335 && (h->a[right].key == key))
336 {
337 index = right;
338 /* current element has already been unlinked, so free it */
339 free(cur);
340 break;
341 }
342
343 /* if left child exists, and our key is smaller, add the child to the
344 * list of nodes to be processed */
345 if ((left <= h->size) && (h->a[left].value >= value ))
346 {
347 assert(new = malloc(sizeof(struct list_elt)));
348 new->i = left;
349 new->next = NULL;
350 /* if list not empty, link in this element */
351 if (last)
352 {
353 last->next = new;
354 }
355 last = new;
356 /* if list was empty, this is going to be the only element */
357 if (! first)
358 {
359 first = new;
360 }
361 }
362
363 /* if right child exists, and our key is smaller, add the child to the
364 * list of nodes to be processed */
365 if ((right <= h->size) && (h->a[right].value >= value ))
366 {
367 assert(new = malloc(sizeof(struct list_elt)));
368 new->i = right;
369 new->next = NULL;
370 /* if list not empty, link in this element */
371 if (last)
372 {
373 last->next = new;
374 }
375 last = new;
376 /* if list was empty, this is going to be the only element */
377 if (! first)
378 {
379 first = new;
380 }
381 }
382
383 /* done adding elements. We've already took care of unlinking, so simply
384 * free the element */
385 free(cur);
386 }
387
388 /* now go deallocate remaining elements in the list */
389 while (first)
390 {
391 cur = first;
392 first = first->next;
393 free(cur);
394 }
395
396 /* done. if nothing found, will return original (negative) value */
397 return index;
398 }
399
400 /* find an element with an 'oldkey', and replace its value with 'newkey'. Data
401 * associated with an element is not touched (ie. its the same element, it just
402 * has a new key/position
403 *
404 * negative value is returned if we can't find the 'oldkey' element */
405 int
406 heap_change_key_value(struct heap *h, unsigned long key, unsigned long oldval,
407 unsigned long newval)
408 {
409 assert(h);
410
411 if (oldval > newval) /* we're decreasing key value */
412 {
413 int node;
414
415 if (0 > (node = find_position(h, key, oldval)))
416 {
417 return -1;
418 }
419
420 /* new value is smaller then old value. All we have to do is set the
421 * value, and propagate element "down" to the proper location. Simple
422 * heapify() ! */
423 h->a[node].value = newval;
424 heapify(h, node);
425
426 return 1;
427 }
428 else if (oldval < newval) /* we're increasing key value */
429 {
430 int node;
431 int parent;
432 struct heap_item temp; /* temporary for exchanging values */
433
434 if (0 > (node = find_position(h, key, oldval)))
435 {
436 return -1;
437 }
438
439 /* increase the value of the node */
440 h->a[node].value = newval;
441
442 /*
443 * now propagate this new value to its proper position in the heap, in
444 * order to maintain the heap property
445 */
446
447 /* parent of the root node is index 0, so when we reach that, we stop
448 * looking (sine can't propagate any further, obviously) */
449 while ((parent = PARENT(node)) > 0)
450 {
451 /* if we're not increasing the value enough to jump over the parent,
452 * we dont have anything to do, since binary heaps do not say much
453 * about relationship of siblings. Only that both are less then the
454 * parent */
455 if (h->a[node].value <= h->a[parent].value)
456 {
457 return 1;
458 }
459
460 /* swap with parent. since we're swapping with parent, heap property
461 * is going to be intact for this subtree after the swap (since
462 * parents value must've been bigger then that of the current node
463 * before modification) */
464 temp = h->a[parent];
465 h->a[parent] = h->a[node];
466 h->a[node] = temp;
467 /* update info as to which node we'll be looking at next */
468 node = parent;
469 }
470
471 return 1;
472 }
473 else /* this is pretty unlikely, but check anyway */
474 {
475 return 1;
476 }
477 }
478
479 void
480 test(void)
481 {
482 struct heap *h = NULL;
483 unsigned long key;
484 unsigned long data;
485
486 h = heap_alloc();
487
488 heap_insert(h, 0, 1);
489 heap_insert(h, 0, 4);
490 heap_insert(h, 0, 2);
491 heap_insert(h, 0, 7);
492 heap_insert(h, 0, 16);
493 heap_insert(h, 0, 3);
494 heap_insert(h, 0, 10);
495 heap_insert(h, 0, 9);
496 heap_insert(h, 0, 14);
497 heap_insert(h, 0, 8);
498
499 printf("After insertions: ");
500 heap_print(h);
501
502 printf("find_position( 0, 1) = %d\n", find_position(h, 0, 1));
503 printf("find_position( 0, 4) = %d\n", find_position(h, 0, 4));
504 printf("find_position( 0, 2) = %d\n", find_position(h, 0, 2));
505 printf("find_position( 0, 7) = %d\n", find_position(h, 0, 7));
506 printf("find_position( 0, 16) = %d\n", find_position(h, 0, 16));
507 printf("find_position( 0, 3) = %d\n", find_position(h, 0, 3));
508 printf("find_position( 0, 10) = %d\n", find_position(h, 0, 10));
509 printf("find_position( 0, 9) = %d\n", find_position(h, 0, 9));
510 printf("find_position( 0, 14) = %d\n", find_position(h, 0, 14));
511 printf("find_position( 0, 8) = %d\n", find_position(h, 0, 8));
512
513 printf("now check increasing key values\n");
514
515 if (0 < (heap_change_key_value(h, 0, 1, 17)))
516 {
517 printf("After heap_change_key_value(h, 0, 1, 17): ");
518 heap_print(h);
519 }
520
521 if (0 < (heap_change_key_value(h, 0, 17, 1)))
522 {
523 printf("After heap_change_key_value(h, 0, 17, 1): ");
524 heap_print(h);
525 }
526
527 if (0 < (heap_change_key_value(h, 0, 4, 15)))
528 {
529 printf("After heap_change_key_value(h, 0, 4, 15): ");
530 heap_print(h);
531 }
532
533 if (0 < (heap_extract_max(h, &key, &data)))
534 {
535 printf("[%lu] ", key);
536 heap_print(h);
537 }
538 else
539 {
540 printf("done!\n");
541 }
542 if (0 < (heap_extract_max(h, &key, &data)))
543 {
544 printf("[%lu] ", key);
545 heap_print(h);
546 }
547 else
548 {
549 printf("done!\n");
550 }
551 if (0 < (heap_extract_max(h, &key, &data)))
552 {
553 printf("[%lu] ", key);
554 heap_print(h);
555 }
556 else
557 {
558 printf("done!\n");
559 }
560 if (0 < (heap_extract_max(h, &key, &data)))
561 {
562 printf("[%lu] ", key);
563 heap_print(h);
564 }
565 else
566 {
567 printf("done!\n");
568 }
569 if (0 < (heap_extract_max(h, &key, &data)))
570 {
571 printf("[%lu] ", key);
572 heap_print(h);
573 }
574 else
575 {
576 printf("done!\n");
577 }
578 if (0 < (heap_extract_max(h, &key, &data)))
579 {
580 printf("[%lu] ", key);
581 heap_print(h);
582 }
583 else
584 {
585 printf("done!\n");
586 }
587 if (0 < (heap_extract_max(h, &key, &data)))
588 {
589 printf("[%lu] ", key);
590 heap_print(h);
591 }
592 else
593 {
594 printf("done!\n");
595 }
596 if (0 < (heap_extract_max(h, &key, &data)))
597 {
598 printf("[%lu] ", key);
599 heap_print(h);
600 }
601 else
602 {
603 printf("done!\n");
604 }
605 if (0 < (heap_extract_max(h, &key, &data)))
606 {
607 printf("[%lu] ", key);
608 heap_print(h);
609 }
610 else
611 {
612 printf("done!\n");
613 }
614 if (0 < (heap_extract_max(h, &key, &data)))
615 {
616 printf("[%lu] ", key);
617 heap_print(h);
618 }
619 else
620 {
621 printf("done!\n");
622 }
623
624 if (0 < (heap_extract_max(h, &key, &data)))
625 {
626 printf("[%lu] ", key);
627 heap_print(h);
628 }
629 else
630 {
631 printf("done!\n");
632 }
633
634 heap_destroy(h);
635 }
636
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.