gclib2/modules/Misc/dheapsort.cxx

   1 /*
   2  * (c) Oleg Puchinin 2006
   3  * graycardinalster@gmail.com
   4  *
   5  */
   6
   7 #include <unistd.h>
   8 #include <stdlib.h>
   9 #include <stdint.h>
  10 #include <string.h>
  11 #include "gclib2.h"
  12
  13 /// Инициализировать кучу для N элементов.
  14 DHeapSort::DHeapSort (int n)
  15 {
  16         size = 0;
  17         h = (char **) malloc (sizeof (char *) * n+10);
  18 }
  19
  20 DHeapSort::~DHeapSort()
  21 {
  22         if (h)
  23                 free (h);
  24 }
  25
  26 /// Добавить элемент.
  27 char * DHeapSort::add(char * x)
  28 {
  29         h[++size]=x;
  30         checkup(size);
  31         return x;
  32 }
  33
  34 /// Выбрать минимальный элемент.
  35 char * DHeapSort::extract_min()
  36 {
  37         char *x;
  38         if(size <= 0)
  39                 return NULL;
  40         x = h[1];
  41         h[1] = h[size--];
  42         checkdown (1);
  43         return x;
  44 }
  45
  46 void DHeapSort::checkup(int c) {
  47         int p;
  48         char * tmp;
  49         p = c>>1;
  50         if (! p)
  51                 return;
  52         if (strcmp (h[p], h[c]) > 0) {
  53                 tmp = h[p]; h[p] = h[c]; h[c] = tmp;
  54                 checkup(p);
  55         }
  56 }
  57
  58 void DHeapSort::checkdown(int p)
  59 {
  60         int c;
  61         char * tmp;
  62         c = p<<1;
  63         if (c > size)
  64                 return;
  65         if ( ((c+1) <= size) && strcmp (h[c + 1], h[c]) < 0)
  66                 ++c;
  67         if (strcmp (h[c], h[p]) < 0) {
  68                 tmp =  h[c];
  69                 h[c] = h[p];
  70                 h[p] = tmp;
  71                 checkdown (c);
  72         }
  73 }
  74