ucw/heap.h

   1 /*
   2  *      UCW Library -- Universal Heap Macros
   3  *
   4  *      (c) 2001 Martin Mares <mj@ucw.cz>
   5  *      (c) 2005 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 usage. */
  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 usage. */
  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 unordered array @heap of @num elements to become a valid heap. The time complexity is linear.
  72  **/
  73 #define HEAP_INIT(type,heap,num,less,swap)                                              \
  74   do {                                                                                  \
  75     uns _i = num;                                                                       \
  76     uns _j, _l;                                                                         \
  77     type x;                                                                             \
  78     while (_i >= 1)                                                                     \
  79       {                                                                                 \
  80         _j = _i;                                                                        \
  81         HEAP_BUBBLE_DOWN_J(heap,num,less,swap)                                          \
  82         _i--;                                                                           \
  83       }                                                                                 \
  84   } while(0)
  85
  86 /**
  87  * Delete the minimum element `heap[1]` in `O(log(n))` time.
  88  * The removed value is moved just after the resulting heap (`heap[num + 1]`).
  89  **/
  90 #define HEAP_DELMIN(type,heap,num,less,swap)                                            \
  91   do {                                                                                  \
  92     uns _j, _l;                                                                         \
  93     type x;                                                                             \
  94     swap(heap,1,num,x);                                                                 \
  95     num--;                                                                              \
  96     _j = 1;                                                                             \
  97     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
  98   } while(0)
  99
 100 /**
 101  * Insert `heap[num]` in `O(log(n))` time. The value of @num must be increased before.
 102  **/
 103 #define HEAP_INSERT(type,heap,num,less,swap)                                            \
 104   do {                                                                                  \
 105     uns _j, _u;                                                                         \
 106     type x;                                                                             \
 107     _j = num;                                                                           \
 108     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 109   } while(0)
 110
 111 /**
 112  * If you need to increase the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
 113  * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
 114  * The time complexity is `O(log(n))`.
 115  **/
 116 #define HEAP_INCREASE(type,heap,num,less,swap,pos)                                      \
 117   do {                                                                                  \
 118     uns _j, _l;                                                                         \
 119     type x;                                                                             \
 120     _j = pos;                                                                           \
 121     HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                             \
 122   } while(0)
 123
 124 /**
 125  * If you need to decrease the value of `heap[pos]`, just do it and then call this macro to rebuild the heap.
 126  * Only `heap[pos]` can be changed, the rest of the array must form a valid heap.
 127  * The time complexity is `O(log(n))`.
 128  **/
 129 #define HEAP_DECREASE(type,heap,num,less,swap,pos)                                      \
 130   do {                                                                                  \
 131     uns _j, _u;                                                                         \
 132     type x;                                                                             \
 133     _j = pos;                                                                           \
 134     HEAP_BUBBLE_UP_J(heap,num,less,swap);                                               \
 135   } while(0)
 136
 137 /**
 138  * Delete `heap[pos]` in `O(log(n))` time.
 139  **/
 140 #define HEAP_DELETE(type,heap,num,less,swap,pos)                                        \
 141   do {                                                                                  \
 142     uns _j, _l, _u;                                                                     \
 143     type x;                                                                             \
 144     _j = pos;                                                                           \
 145     swap(heap,_j,num,x);                                                                \
 146     num--;                                                                              \
 147     if (less(heap[_j], heap[num+1]))                                                    \
 148       HEAP_BUBBLE_UP_J(heap,num,less,swap)                                              \
 149     else                                                                                \
 150       HEAP_BUBBLE_DOWN_J(heap,num,less,swap);                                           \
 151   } while(0)
 152
 153 /**
 154  * Default swapping macro.
 155  **/
 156 #define HEAP_SWAP(heap,a,b,t) (t=heap[a], heap[a]=heap[b], heap[b]=t)