2 * UCW Library -- Universal Heap Macros
4 * (c) 2001--2012 Martin Mares <mj@ucw.cz>
5 * (c) 2005--2012 Tomas Valla <tom@ucw.cz>
7 * This software may be freely distributed and used according to the terms
8 * of the GNU Lesser General Public License.
16 * Binary heap is a simple data structure, which for example supports efficient insertions, deletions
17 * and access to the minimal inserted item. We define several macros for such operations.
18 * Note that because of simplicity of heaps, we have decided to define direct macros instead
19 * of a <<generic:,macro generator>> as for several other data structures in the Libucw.
21 * A heap is represented by a number of elements and by an array of values. Beware that we
22 * index this array from one, not from zero as do the standard C arrays.
24 * Most macros use these parameters:
26 * - @type - the type of elements
27 * - @num - a variable (signed or unsigned integer) with the number of elements
28 * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused
29 * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y
30 * - @swap - a callback to swap two array elements; `swap(heap, i, j, t)` must swap `heap[i]` with `heap[j]` with possible help of temporary variable @t (type @type).
32 * A valid heap must follow these rules:
35 * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
37 * The first element `heap[1]` is always lower or equal to all other elements.
44 /* For internal use. */
45 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
51 if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1]))) \
53 if (_l != num && less(heap[_l+1],heap[_l])) \
59 /* For internal use. */
60 #define HEAP_BUBBLE_UP_J(heap,num,less,swap) \
64 if (less(heap[_u], heap[_j])) \
71 * Shuffle the items `heap[1]`, ..., `heap[num]` to get a valid heap.
72 * This operation takes linear time.
74 #define HEAP_INIT(type,heap,num,less,swap) \
82 HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \
88 * Delete the minimum element `heap[1]` in `O(log(n))` time. The @num variable is decremented.
89 * The removed value is moved just after the resulting heap (`heap[num + 1]`).
91 #define HEAP_DELETE_MIN(type,heap,num,less,swap) \
98 HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
102 * Insert a new element @elt to the heap. The @num variable is incremented.
103 * This operation takes `O(log(n))` time.
105 #define HEAP_INSERT(type,heap,num,less,swap,elt) \
111 HEAP_BUBBLE_UP_J(heap,num,less,swap); \
115 * Increase `heap[pos]` to a new value @elt (greater or equal to the previous value).
116 * The time complexity is `O(log(n))`.
118 #define HEAP_INCREASE(type,heap,num,less,swap,pos,elt) \
124 HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \
128 * Decrease `heap[pos]` to a new value @elt (less or equal to the previous value).
129 * The time complexity is `O(log(n))`.
131 #define HEAP_DECREASE(type,heap,num,less,swap,pos,elt) \
137 HEAP_BUBBLE_UP_J(heap,num,less,swap); \
141 * Change `heap[pos]` to a new value @elt. The time complexity is `O(log(n))`.
142 * If you know that the new value is always smaller or always greater, it is faster
143 * to use `HEAP_DECREASE` or `HEAP_INCREASE` respectively.
145 #define HEAP_REPLACE(type,heap,num,less,swap,pos,elt) \
148 if (less(heap[pos], _elt)) \
149 HEAP_INCREASE(type,heap,num,less,swap,pos,_elt); \
151 HEAP_DECREASE(type,heap,num,less,swap,pos,_elt); \
155 * Replace the minimum `heap[pos]` by a new value @elt. The time complexity is `O(log(n))`.
157 #define HEAP_REPLACE_MIN(type,heap,num,less,swap,elt) \
158 HEAP_INCREASE(type,heap,num,less,swap,1,elt)
161 * Delete an arbitrary element, given by its position. The @num variable is decremented.
162 * The operation takes `O(log(n))` time.
164 #define HEAP_DELETE(type,heap,num,less,swap,pos) \
167 HEAP_REPLACE(type,heap,num,less,swap,pos,heap[num+1]); \
171 * Default swapping macro.
173 #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)