X-Git-Url: http://mj.ucw.cz/gitweb/?a=blobdiff_plain;ds=sidebyside;f=ucw%2Fheap.h;h=74e8a12445c39a266b66a465c8c6d4f7b7d97454;hb=97d134124cb7f43e34a976e0d6a79622c67cb455;hp=4f83776f5cb0dff38dbf646a702b23775926ebed;hpb=031256ad2e123eec58521f8e3eb9496c197641d2;p=libucw.git diff --git a/ucw/heap.h b/ucw/heap.h index 4f83776f..74e8a124 100644 --- a/ucw/heap.h +++ b/ucw/heap.h @@ -1,13 +1,57 @@ /* * UCW Library -- Universal Heap Macros * - * (c) 2001 Martin Mares - * (c) 2005 Tomas Valla + * (c) 2001--2012 Martin Mares + * (c) 2005--2012 Tomas Valla * * 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 <> 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. + * + * Position tracking + * ----------------- + * + * As a heap does not support efficient lookup of an element by value, all functions + * acting on existing heap elements need to obtain the position of the element in the + * heap. This position has to be tracked by the caller, usually in the supplied swap + * callback. + * + * However, there are some caveats noted in the descriptions of individual functions. + * + * [[macros]] + * Macros + * ------ + ***/ + +/* For internal use. */ #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap) \ for (;;) \ { \ @@ -22,6 +66,7 @@ _j = _l; \ } +/* For internal use. */ #define HEAP_BUBBLE_UP_J(heap,num,less,swap) \ while (_j > 1) \ { \ @@ -32,6 +77,12 @@ _j = _u; \ } +/** + * Shuffle the items `heap[1]`, ..., `heap[num]` to get a valid heap. + * This operation takes linear time. + * + * Position tracking: Position of `heap[i]` must be initialized to `i` before calling. + **/ #define HEAP_INIT(type,heap,num,less,swap) \ do { \ uns _i = num; \ @@ -45,32 +96,98 @@ } \ } while(0) -#define HEAP_DELMIN(type,heap,num,less,swap) \ +/** + * Delete the minimum element `heap[1]` in `O(log(n))` time. The @num variable is decremented. + * The removed value is moved just after the resulting heap (`heap[num + 1]`). + * + * Position tracking: Fully automatic. + **/ +#define HEAP_DELETE_MIN(type,heap,num,less,swap) \ do { \ uns _j, _l; \ type x; \ swap(heap,1,num,x); \ - num--; \ + num--; \ _j = 1; \ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) -#define HEAP_INSERT(type,heap,num,less,swap) \ +/** + * Insert a new element @elt to the heap. The @num variable is incremented. + * This operation takes `O(log(n))` time. + * + * Position tracking: The position of the new element must be initialized to @num+1 + * before calling this macro. + **/ +#define HEAP_INSERT(type,heap,num,less,swap,elt) \ do { \ uns _j, _u; \ type x; \ + heap[++num] = elt; \ _j = num; \ HEAP_BUBBLE_UP_J(heap,num,less,swap); \ } while(0) -#define HEAP_INCREASE(type,heap,num,less,swap,pos) \ +/** + * Increase `heap[pos]` to a new value @elt (greater or equal to the previous value). + * The time complexity is `O(log(n))`. + * + * Position tracking: Fully automatic. + **/ +#define HEAP_INCREASE(type,heap,num,less,swap,pos,elt) \ do { \ uns _j, _l; \ type x; \ + heap[pos] = elt; \ _j = pos; \ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) +/** + * Decrease `heap[pos]` to a new value @elt (less or equal to the previous value). + * The time complexity is `O(log(n))`. + * + * Position tracking: Fully automatic. + **/ +#define HEAP_DECREASE(type,heap,num,less,swap,pos,elt) \ + do { \ + uns _j, _u; \ + type x; \ + heap[pos] = elt; \ + _j = pos; \ + HEAP_BUBBLE_UP_J(heap,num,less,swap); \ + } while(0) + +/** + * Change `heap[pos]` to a new value @elt. The time complexity is `O(log(n))`. + * If you know that the new value is always smaller or always greater, it is faster + * to use `HEAP_DECREASE` or `HEAP_INCREASE` respectively. + * + * Position tracking: Fully automatic. + **/ +#define HEAP_REPLACE(type,heap,num,less,swap,pos,elt) \ + do { \ + type _elt = elt; \ + if (less(heap[pos], _elt)) \ + HEAP_INCREASE(type,heap,num,less,swap,pos,_elt); \ + else \ + HEAP_DECREASE(type,heap,num,less,swap,pos,_elt); \ + } while(0) + +/** + * Replace the minimum `heap[pos]` by a new value @elt. The time complexity is `O(log(n))`. + * + * Position tracking: Fully automatic. + **/ +#define HEAP_REPLACE_MIN(type,heap,num,less,swap,elt) \ + HEAP_INCREASE(type,heap,num,less,swap,1,elt) + +/** + * Delete an arbitrary element, given by its position. The @num variable is decremented. + * The operation takes `O(log(n))` time. + * + * Position tracking: Fully automatic. + **/ #define HEAP_DELETE(type,heap,num,less,swap,pos) \ do { \ uns _j, _l, _u; \ @@ -84,5 +201,7 @@ HEAP_BUBBLE_DOWN_J(heap,num,less,swap); \ } while(0) -/* Default swapping macro */ +/** + * Default swapping macro. + **/ #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)