diff options
Diffstat (limited to 'lib/heap.h')
| -rw-r--r-- | lib/heap.h | 156 |
1 files changed, 156 insertions, 0 deletions
diff --git a/lib/heap.h b/lib/heap.h new file mode 100644 index 00000000..c8c3d348 --- /dev/null +++ b/lib/heap.h @@ -0,0 +1,156 @@ +/* + * UCW Library -- Universal Heap Macros + * + * (c) 2001 Martin Mares <mj@ucw.cz> + * (c) 2005 Tomas Valla <tom@ucw.cz> + * + * This software may be freely distributed and used according to the terms + * of the GNU Lesser General Public License. + */ + +/** + * [[intro]] + * Introduction + * ------------ + * + * Binary heap is a simple data structure, which for example supports efficient insertions, deletions + * and access to the minimal inserted item. We define several macros for such operations. + * Note that because of simplicity of heaps, we have decided to define direct macros instead + * of a <<generic:,macro generator>> as for several other data structures in the Libucw. + * + * A heap is represented by a number of elements and by an array of values. Beware that we + * index this array from one, not from zero as do the standard C arrays. + * + * Most macros use these parameters: + * + * - @type - the type of elements + * - @num - a variable (signed or unsigned integer) with the number of elements + * - @heap - a C array of type @type; the heap is stored in `heap[1] .. heap[num]`; `heap[0]` is unused + * - @less - a callback to compare two element values; `less(x, y)` shall return a non-zero value iff @x is lower than @y + * - @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). + * + * A valid heap must follow these rules: + * + * - `num >= 0` + * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]` + * + * The first element `heap[1]` is always lower or equal to all other elements. + * + * [[macros]] + * Macros + * ------ + */ + +/* For internal usage. */ +#define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ + for (;;) \ + { \ + _l = 2*_j; \ + if (_l > num) \ + break; \ + if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1]))) \ + break; \ + if (_l != num && less(heap[_l+1],heap[_l])) \ + _l++; \ + swap(heap,_j,_l,x); \ + _j = _l; \ + } + +/* For internal usage. */ +#define HEAP_BUBBLE_UP_J(heap,num,less,swap) \ + while (_j > 1) \ + { \ + _u = _j/2; \ + if (less(heap[_u], heap[_j])) \ + break; \ + swap(heap,_u,_j,x); \ + _j = _u; \ + } + +/** + * Shuffle the unordered array @heap of @num elements to become a valid heap. The time complexity is linear. + **/ +#define HEAP_INIT(heap,num,type,less,swap) \ + do { \ + uint _i = num; \ + uint _j, _l; \ + type x; \ + while (_i >= 1) \ + { \ + _j = _i; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ + _i--; \ + } \ + } while(0) + +/** + * Delete the minimum element `heap[1]` in `O(log(n))` time. + * The removed value is moved just after the resulting heap (`heap[num + 1]`). + **/ +#define HEAP_DELMIN(heap,num,type,less,swap) \ + do { \ + uint _j, _l; \ + type x; \ + swap(heap,1,num,x); \ + num--; \ + _j = 1; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before. + **/ +#define HEAP_INSERT(heap,num,type,less,swap) \ + do { \ + uint _j, _u; \ + type x; \ + _j = num; \ + HEAP_BUBBLE_UP_J(heap,num,less,swap); \ + } while(0) + +/** + * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. + * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. + * The time complexity is `O(log(n))`. + **/ +#define HEAP_INCREASE(heap,num,type,less,swap,pos) \ + do { \ + uint _j, _l; \ + type x; \ + _j = pos; \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap. + * Only `heap[pos]` can be changed, the rest of the array must form a valid heap. + * The time complexity is `O(log(n))`. + **/ +#define HEAP_DECREASE(heap,num,type,less,swap,pos) \ + do { \ + uint _j, _u; \ + type x; \ + _j = pos; \ + HEAP_BUBBLE_UP_J(heap,num,less,swap); \ + } while(0) + +/** + * Delete `heap[pos]` in `O(log(n))` time. + **/ +#define HEAP_DELETE(heap,num,type,less,swap,pos) \ + do { \ + uint _j, _l, _u; \ + type x; \ + _j = pos; \ + swap(heap,_j,num,x); \ + num--; \ + if (less(heap[_j], heap[num+1])) \ + HEAP_BUBBLE_UP_J(heap,num,less,swap) \ + else \ + HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ + } while(0) + +/** + * Default swapping macro. + **/ +#define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t) |