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  * [[macros]]
  40  * Macros
  41  * ------
  42  ***/
  43
  44 /* For internal use. */
  45 #define HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  46   for (;;)                                                                              \
  47     {                                                                                   \
  48       _l = 2*_j;                                                                        \
  49       if (_l > num)                                                                     \
  50         break;                                                                          \
  51       if (less(heap[_j],heap[_l]) && (_l == num || less(heap[_j],heap[_l+1])))          \
  52         break;                                                                          \
  53       if (_l != num && less(heap[_l+1],heap[_l]))                                       \
  54         _l++;                                                                           \
  55       swap(heap,_j,_l,x);                                                               \
  56       _j = _l;                                                                          \
  57     }
  58
  59 /* For internal use. */
  60 #define HEAP_BUBBLE_UP_J(heap,num,less,swap)                                            \
  61   while (_j > 1)                                                                        \
  62     {                                                                                   \
  63       _u = _j/2;                                                                        \
  64       if (less(heap[_u], heap[_j]))                                                     \
  65         break;                                                                          \
  66       swap(heap,_u,_j,x);                                                               \
  67       _j = _u;                                                                          \
  68     }
  69
  70 /**
  71  * Shuffle the items `heap[1]`, ..., `heap[num]` to get a valid heap.
  72  * This operation takes linear time.
  73  **/
  74 #define HEAP_INIT(type,heap,num,less,swap)                                              \
  75   do {                                                                                  \
  76     uns _i = num;                                                                       \
  77     uns _j, _l;                                                                         \
  78     type x;                                                                             \
  79     while (_i >= 1)                                                                     \
  80       {                                                                                 \
  81         _j = _i;                                                                        \
  82         HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  83         _i--;                                                                           \
  84       }                                                                                 \
  85   } while(0)
  86
  87 /**
  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]`).
  90  **/
  91 #define HEAP_DELETE_MIN(type,heap,num,less,swap)                                        \
  92   do {                                                                                  \
  93     uns _j, _l;                                                                         \
  94     type x;                                                                             \
  95     swap(heap,1,num,x);                                                                 \
  96     num--;                                                                              \
  97     _j = 1;                                                                             \
  98     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  99   } while(0)
 100
 101 /**
 102  * Insert a new element @elt to the heap. The @num variable is incremented.
 103  * This operation takes `O(log(n))` time.
 104  **/
 105 #define HEAP_INSERT(type,heap,num,less,swap,elt)                                        \
 106   do {                                                                                  \
 107     uns _j, _u;                                                                         \
 108     type x;                                                                             \
 109     heap[++num] = elt;                                                                  \
 110     _j = num;                                                                           \
 111     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 112   } while(0)
 113
 114 /**
 115  * Increase `heap[pos]` to a new value @elt (greater or equal to the previous value).
 116  * The time complexity is `O(log(n))`.
 117  **/
 118 #define HEAP_INCREASE(type,heap,num,less,swap,pos,elt)                                  \
 119   do {                                                                                  \
 120     uns _j, _l;                                                                         \
 121     type x;                                                                             \
 122     heap[pos] = elt;                                                                    \
 123     _j = pos;                                                                           \
 124     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
 125   } while(0)
 126
 127 /**
 128  * Decrease `heap[pos]` to a new value @elt (less or equal to the previous value).
 129  * The time complexity is `O(log(n))`.
 130  **/
 131 #define HEAP_DECREASE(type,heap,num,less,swap,pos,elt)                                  \
 132   do {                                                                                  \
 133     uns _j, _u;                                                                         \
 134     type x;                                                                             \
 135     heap[pos] = elt;                                                                    \
 136     _j = pos;                                                                           \
 137     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 138   } while(0)
 139
 140 /**
 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.
 144  **/
 145 #define HEAP_REPLACE(type,heap,num,less,swap,pos,elt)                                   \
 146   do {                                                                                  \
 147     type _elt = elt;                                                                    \
 148     if (less(heap[pos], _elt))                                                          \
 149       HEAP_INCREASE(type,heap,num,less,swap,pos,_elt);                                  \
 150     else                                                                                \
 151       HEAP_DECREASE(type,heap,num,less,swap,pos,_elt);                                  \
 152   } while(0)
 153
 154 /**
 155  * Replace the minimum `heap[pos]` by a new value @elt. The time complexity is `O(log(n))`.
 156  **/
 157 #define HEAP_REPLACE_MIN(type,heap,num,less,swap,elt)                                   \
 158   HEAP_INCREASE(type,heap,num,less,swap,1,elt)
 159
 160 /**
 161  * Delete an arbitrary element, given by its position. The @num variable is decremented.
 162  * The operation takes `O(log(n))` time.
 163  **/
 164 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
 165   do {                                                                                  \
 166     num--;                                                                              \
 167     HEAP_REPLACE(type,heap,num,less,swap,pos,heap[num+1]);                              \
 168   } while(0)
 169
 170 /**
 171  * Default swapping macro.
 172  **/
 173 #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)