home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / src / basic / _k_heap.c < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.1 KB  |  184 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  _k_heap.c
  7. +
  8. +
  9. +  Copyright (c) 1991  by  Max-Planck-Institut fuer Informatik
  10. +  Im Stadtwald, 6600 Saarbruecken, FRG     
  11. +  All rights reserved.
  12. + 
  13. *******************************************************************************/
  14.  
  15.  
  16. #include <LEDA/k_heap.h>
  17.  
  18. #define SON1(i)   (K*i+1)
  19. #define PARENT(i) ((i-1)/K)
  20.  
  21.  
  22. K_HEAP::K_HEAP(int n, int k)  
  23. { 
  24.   K = k;
  25.   Key = new ent[n]; 
  26.   Inf = new ent[n]; 
  27.   Item = new int[n];
  28.   Pos = new int[n+1];
  29.   for (int i=1;i<=n;i++) free_items.append(Ent(i));
  30.   max_count = n; count = 0; 
  31. }
  32.  
  33. K_HEAP::~K_HEAP()  
  34. { 
  35.   delete Key; 
  36.   delete Inf;
  37.   delete Item;
  38.   delete Pos;
  39.   free_items.clear();
  40. }
  41.  
  42. void K_HEAP::clear()
  43. { count = 0;
  44.   free_items.clear();
  45.   for (int i=1;i<=max_count;i++) free_items.append(Ent(i));
  46. }
  47.  
  48. void  K_HEAP::rise(int& pos, ent k, ent i)
  49. {
  50.   register int parent = PARENT(pos);
  51.  
  52.   while (pos > 0 && cmp(Inf[parent],i) > 0 )
  53.     { Inf[pos] = Inf[parent];
  54.       Key[pos] = Key[parent];
  55.       Item[pos] = Item[parent];
  56.       Pos[Item[pos]] = pos;
  57.       pos = parent;
  58.       parent = PARENT(pos);
  59.      }
  60.  
  61.   Inf[pos] = i;
  62.   Key[pos] = k;
  63.  
  64. }
  65.  
  66. void K_HEAP::sink(int& current, ent k, ent i)
  67. {
  68.   register int child   = SON1(current);
  69.  
  70.   while (child < count)
  71.   { 
  72.     int r = Min(count,child+K);
  73.     for (int j=child+1;j<r;j++)
  74.       if (cmp(Inf[j],Inf[child])<0 ) child = j;
  75.  
  76.     if (cmp(i,Inf[child])>0) 
  77.      { Inf[current] = Inf[child];
  78.        Key[current] = Key[child];
  79.        Item[current] = Item[child];
  80.        Pos[Item[current]] = current;
  81.        current = child;
  82.        child = SON1(current);
  83.       }
  84.     else  break;
  85.    }
  86.  
  87.   Inf[current] = i;
  88.   Key[current] = k;
  89. }
  90.  
  91.  
  92. void K_HEAP::decrease_inf(int it, ent i)
  93. {
  94.   int pos = Pos[it];
  95.   if (cmp(Inf[pos],i)<0) 
  96.   { cout << string ("INF = %d  i = %d\n",Inf[pos],i);
  97.     cout.flush();
  98.     error_handler(1,"k-heap: inf too large in decrease_inf");
  99.   }
  100.  
  101.   rise(pos,Key[pos],i);
  102.   Pos[it] = pos;
  103.   Item[pos] = it;
  104. }
  105.  
  106.  
  107. int K_HEAP::insert(ent k, ent i) 
  108. {
  109.   if (free_items.empty()) error_handler(1,"k_heap: overflow");
  110.  
  111.   int new_it = (int)free_items.head();
  112.   free_items.pop();
  113.  
  114.   int p = count++;
  115.  
  116.   rise(p,k,i);
  117.  
  118.   Pos[new_it] = p;
  119.   Item[p] = new_it;
  120.  
  121.   return new_it;
  122. }
  123.  
  124. int K_HEAP::insert0(ent k, ent i) 
  125. {
  126.   if (free_items.empty()) error_handler(1,"k_heap: overflow");
  127.  
  128.   int new_it = (int)free_items.head();
  129.   free_items.pop();
  130.  
  131.   Key[count] = k;
  132.   Inf[count] = i;
  133.   Item[count] = new_it;
  134.   Pos[new_it] = count;
  135.   count++;
  136.  
  137.   return new_it;
  138. }
  139.  
  140.  
  141.  
  142. ent K_HEAP::del_item(int it)
  143. {
  144.   int p = Pos[it];
  145.  
  146.   ent result = Key[p];
  147.  
  148.   count--;
  149.  
  150.   free_items.append(Ent(it));
  151.  
  152.   sink(p,Key[count],Inf[count]);
  153.  
  154.   Item[p] = Item[count];
  155.   Pos[Item[p]]= p;
  156.  
  157.   return result;
  158. }
  159.  
  160. void K_HEAP::print()
  161. { 
  162.   int i;
  163.  
  164.   for(i=0;i<count;i++) 
  165.     { print_key(Key[i]);
  166.       cout << "-";
  167.       print_inf(Inf[i]);
  168.       cout << "  ";
  169.      }
  170.   newline;
  171.  
  172.  
  173.   cout << "ITEM: ";
  174.   for(i=0;i<count;i++) cout << string(" %3d",Item[i]);
  175.   newline;
  176.  
  177.   cout << "POS:  ";
  178.   for(i=0;i<count;i++) cout << string(" %3d",Pos[Item[i]]);
  179.   newline;
  180.  
  181.   newline;
  182.  
  183. }
  184.