ucw/heap.h

   1 /*
   2  *      UCW Library -- Universal Heap Macros
   3  *
   4  *      (c) 2001--2012 Martin Mares <mj@ucw.cz>
   5  *      (c) 2005--2012 Tomas Valla <tom@ucw.cz>
   6  *
   7  *      This software may be freely distributed and used according to the terms
   8  *      of the GNU Lesser General Public License.
   9  */
  10
  11 /***
  12  * [[intro]]
  13  * Introduction
  14  * ------------
  15  *
  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.
  20  *
  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.
  23  *
  24  * Most macros use these parameters:
  25  *
  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).
  31  *
  32  * A valid heap must follow these rules:
  33  *
  34  * - `num >= 0`
  35  * - `heap[i] >= heap[i / 2]` for each `i` in `[2, num]`
  36  *
  37  * The first element `heap[1]` is always lower or equal to all other elements.
  38  *
  39  * Position tracking
  40  * -----------------
  41  *
  42  * As a heap does not support efficient lookup of an element by value, all functions
  43  * acting on existing heap elements need to obtain the position of the element in the
  44  * heap. This position has to be tracked by the caller, usually in the supplied swap
  45  * callback.
  46  *
  47  * However, there are some caveats noted in the descriptions of individual functions.
  48  *
  49  * [[macros]]
  50  * Macros
  51  * ------
  52  ***/
  53
  54 /* For internal use. */
  55 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  56   for (;;)                                                                              \
  57     {                                                                                   \
  58       _l = 2*_j;                                                                        \
  59       if (_l > num)                                                                     \
  60         break;                                                                          \
  61       if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1])))          \
  62         break;                                                                          \
  63       if (_l != num && less(heap[_l+1],heap[_l]))                                       \
  64         _l++;                                                                           \
  65       swap(heap,_j,_l,x);                                                               \
  66       _j = _l;                                                                          \
  67     }
  68
  69 /* For internal use. */
  70 #define HEAP_BUBBLE_UP_J(heap,num,less,swap)                                            \
  71   while (_j > 1)                                                                        \
  72     {                                                                                   \
  73       _u = _j/2;                                                                        \
  74       if (less(heap[_u], heap[_j]))                                                     \
  75         break;                                                                          \
  76       swap(heap,_u,_j,x);                                                               \
  77       _j = _u;                                                                          \
  78     }
  79
  80 /**
  81  * Shuffle the items `heap[1]`, ..., `heap[num]` to get a valid heap.
  82  * This operation takes linear time.
  83  *
  84  * Position tracking: Position of `heap[i]` must be initialized to `i` before calling.
  85  **/
  86 #define HEAP_INIT(type,heap,num,less,swap)                                              \
  87   do {                                                                                  \
  88     uns _i = num;                                                                       \
  89     uns _j, _l;                                                                         \
  90     type x;                                                                             \
  91     while (_i >= 1)                                                                     \
  92       {                                                                                 \
  93         _j = _i;                                                                        \
  94         HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  95         _i--;                                                                           \
  96       }                                                                                 \
  97   } while(0)
  98
  99 /**
 100  * Delete the minimum element `heap[1]` in `O(log(n))` time. The @num variable is decremented.
 101  * The removed value is moved just after the resulting heap (`heap[num + 1]`).
 102  *
 103  * Position tracking: Fully automatic.
 104  **/
 105 #define HEAP_DELETE_MIN(type,heap,num,less,swap)                                        \
 106   do {                                                                                  \
 107     uns _j, _l;                                                                         \
 108     type x;                                                                             \
 109     swap(heap,1,num,x);                                                                 \
 110     num--;                                                                              \
 111     _j = 1;                                                                             \
 112     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
 113   } while(0)
 114
 115 /**
 116  * Insert a new element @elt to the heap. The @num variable is incremented.
 117  * This operation takes `O(log(n))` time.
 118  *
 119  * Position tracking: The position of the new element must be initialized to @num+1
 120  * before calling this macro.
 121  **/
 122 #define HEAP_INSERT(type,heap,num,less,swap,elt)                                        \
 123   do {                                                                                  \
 124     uns _j, _u;                                                                         \
 125     type x;                                                                             \
 126     heap[++num] = elt;                                                                  \
 127     _j = num;                                                                           \
 128     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 129   } while(0)
 130
 131 /**
 132  * Increase `heap[pos]` to a new value @elt (greater or equal to the previous value).
 133  * The time complexity is `O(log(n))`.
 134  *
 135  * Position tracking: Fully automatic.
 136  **/
 137 #define HEAP_INCREASE(type,heap,num,less,swap,pos,elt)                                  \
 138   do {                                                                                  \
 139     uns _j, _l;                                                                         \
 140     type x;                                                                             \
 141     heap[pos] = elt;                                                                    \
 142     _j = pos;                                                                           \
 143     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
 144   } while(0)
 145
 146 /**
 147  * Decrease `heap[pos]` to a new value @elt (less or equal to the previous value).
 148  * The time complexity is `O(log(n))`.
 149  *
 150  * Position tracking: Fully automatic.
 151  **/
 152 #define HEAP_DECREASE(type,heap,num,less,swap,pos,elt)                                  \
 153   do {                                                                                  \
 154     uns _j, _u;                                                                         \
 155     type x;                                                                             \
 156     heap[pos] = elt;                                                                    \
 157     _j = pos;                                                                           \
 158     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 159   } while(0)
 160
 161 /**
 162  * Change `heap[pos]` to a new value @elt. The time complexity is `O(log(n))`.
 163  * If you know that the new value is always smaller or always greater, it is faster
 164  * to use `HEAP_DECREASE` or `HEAP_INCREASE` respectively.
 165  *
 166  * Position tracking: Fully automatic.
 167  **/
 168 #define HEAP_REPLACE(type,heap,num,less,swap,pos,elt)                                   \
 169   do {                                                                                  \
 170     type _elt = elt;                                                                    \
 171     if (less(heap[pos], _elt))                                                          \
 172       HEAP_INCREASE(type,heap,num,less,swap,pos,_elt);                                  \
 173     else                                                                                \
 174       HEAP_DECREASE(type,heap,num,less,swap,pos,_elt);                                  \
 175   } while(0)
 176
 177 /**
 178  * Replace the minimum `heap[pos]` by a new value @elt. The time complexity is `O(log(n))`.
 179  *
 180  * Position tracking: Fully automatic.
 181  **/
 182 #define HEAP_REPLACE_MIN(type,heap,num,less,swap,elt)                                   \
 183   HEAP_INCREASE(type,heap,num,less,swap,1,elt)
 184
 185 /**
 186  * Delete an arbitrary element, given by its position. The @num variable is decremented.
 187  * The operation takes `O(log(n))` time.
 188  *
 189  * Position tracking: Fully automatic.
 190  **/
 191 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
 192   do {                                                                                  \
 193     uns _j, _l, _u;                                                                     \
 194     type x;                                                                             \
 195     _j = pos;                                                                           \
 196     swap(heap,_j,num,x);                                                                \
 197     num--;                                                                              \
 198     if (less(heap[_j], heap[num+1]))                                                    \
 199       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
 200     else                                                                                \
 201       HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                           \
 202   } while(0)
 203
 204 /**
 205  * Default swapping macro.
 206  **/
 207 #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)