home *** CD-ROM | disk | FTP | other *** search
/ Power Programmierung 2 / Power-Programmierung CD 2 (Tewi)(1994).iso / c / library / dos / diverses / leda / incl / k_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  2.0 KB  |  108 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  k_heap.h
  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.  
  17.  
  18. #ifndef KHEAP_H
  19. #define KHEAP_H
  20.  
  21. //------------------------------------------------------------------------------
  22. //
  23. // K-nary Heaps
  24. //
  25. // S. Naeher 1990
  26. //
  27. //------------------------------------------------------------------------------
  28.  
  29.  
  30. #include <LEDA/basic.h>
  31. #include <LEDA/slist.h>
  32.  
  33.  
  34. typedef int k_heap_item;
  35.  
  36.  
  37. class K_HEAP  {
  38.  
  39. virtual int  cmp(ent& x, ent& y){ return int(x)-int(y); }
  40. virtual void print_key(ent& x)  { Print(x); }
  41. virtual void print_inf(ent& x)  { Print(x); }
  42.  
  43. int  K;
  44. ent* Key;
  45. ent* Inf;
  46. int* Pos;
  47. int* Item;
  48.  
  49. SLIST free_items;
  50.  
  51. int count;
  52. int max_count;
  53.  
  54. void rise(int&,ent,ent);
  55. void sink(int&,ent,ent);
  56.  
  57.  
  58. public:
  59.  
  60.  K_HEAP(int,int=2);
  61. ~K_HEAP();
  62.  
  63. int insert(ent k, ent i);
  64. int insert0(ent k, ent i);
  65.  
  66. void decrease_inf(k_heap_item, ent);
  67.  
  68. void change_key(k_heap_item it, ent k) { Key[Pos[it]] = k; }
  69.  
  70. ent del_item(k_heap_item);
  71.  
  72. ent del_min()   { return del_item(Item[0]); }
  73.  
  74. ent  key(int it) const { return Key[Pos[it]]; }
  75. ent  inf(int it) const { return Inf[Pos[it]]; }
  76.  
  77. k_heap_item  find_min()  const { return (count>0) ? Item[0] : 0;  }
  78.  
  79. int  size()    const   { return count;    }
  80. bool empty()   const  { return count==0; }
  81. void clear();
  82.  
  83. void print();
  84.  
  85. };
  86.  
  87. class k_heap : public K_HEAP {
  88.  
  89. virtual int  cmp(ent& x, ent& y){ return int(x)-int(y); }
  90. virtual void print_key(ent& x)  { Print(x); }
  91. virtual void print_inf(ent& x)  { Print(x); }
  92.  
  93. public:
  94.  
  95.  k_heap(int N,int k=2) : K_HEAP(N,k) {};
  96. ~k_heap() {};
  97.  
  98. k_heap_item insert(ent k, int i) { return K_HEAP::insert(k,Ent(i)); };
  99.  
  100. void decrease_inf(k_heap_item it, int x) { K_HEAP::decrease_inf(it,Ent(x)); };
  101.  
  102. int  inf(k_heap_item it) const { return (int)K_HEAP::key(it); }
  103.  
  104. };
  105.  
  106.  
  107. #endif
  108.