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 #ifndef HEAP_H_
33 #define HEAP_H_
34
35 /* implements a binary heap data structure (just as described in the white MIT
36 * algorithms book */
37
38 /* NOTE: this heap is maintained so that element @ position 0 is not used
39 * this makes things much easier to keep track of (no special checks in
40 * PARENT()/LEFT/RIGHT macros, etc */
41
42 struct heap_item
43 {
44 unsigned long key;
45 /* if you'd like to store something weird, just use unsigned long to store
46 * pointers */
47 unsigned long value;
48 };
49
50 struct heap
51 {
52 struct heap_item *a;/* array used to implement a heap data structure */
53 int length; /* # elements in array used for the heap */
54 int size; /* number of elements actually stored in array */
55 };
56
57
58 /* allocate a heap data structure. Heap is empty and unusable until something is
59 * inserted */
60 struct heap * heap_alloc(void);
61 /* deallocate the memory associated with a heap */
62 void heap_destroy(struct heap *h);
63 /* inserts the element in the proper position in the heap, according to the
64 * 'key', and associates 'value' with it. */
65 void heap_insert(struct heap *h, unsigned long key, unsigned long value);
66 /* eventually maybe make it pretty-print. For now, just dump the array */
67 void heap_print(struct heap *h);
68 /* returns 1 if heap is empty, and 0 otherwise */
69 int heap_empty(struct heap *h);
70 /* fills in the values for key and value. returns negative value in case the
71 * heap is empty. Does not modify the heap layout/structure */
72 int heap_peek_max(struct heap *h, unsigned long *key, unsigned long *value);
73 /* removes the element with a max value from the heap */
74 void heap_rmv_max(struct heap *h);
75 /* performs the equivalent of the above two operations: places the key/value
76 * from the maximum-valued heap element into the parameters, then removes the
77 * element from the heap. returns negative if the heap is empty */
78 int heap_extract_max(struct heap *h, unsigned long *key, unsigned long *data);
79 /* given a heap 'h', change value of element described by a 'key' from 'oldval'
80 * to 'newval' */
81 int heap_change_key_value(struct heap *h, unsigned long key,
82 unsigned long oldval, unsigned long newval);
83
84 #endif
85
This page was automatically generated by the
LXR engine.
Visit the LXR main site for more
information.