home *** CD-ROM | disk | FTP | other *** search
/ Power-Programmierung / CD2.mdf / c / library / dos / diverses / leda / incl / f_heap.h < prev    next >
Encoding:
C/C++ Source or Header  |  1991-11-15  |  3.5 KB  |  149 lines
  1. /*******************************************************************************
  2. +
  3. +  LEDA  2.1.1                                                 11-15-1991
  4. +
  5. +
  6. +  f_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 FHEAP_H
  19. #define FHEAP_H
  20.  
  21. //------------------------------------------------------------------------------
  22. //
  23. // Fibonacci Heap
  24. //
  25. // Michael Muth  (1988)
  26. //
  27. // Modifications
  28. //
  29. // - virtual compare function  (Stefan Naeher, August 1989)
  30. //
  31. // - virtual clear functions   (Stefan Naeher, April 1990)
  32. //
  33. //------------------------------------------------------------------------------
  34.  
  35.  
  36. #include <LEDA/basic.h>
  37.  
  38.  
  39. class f_heap_node  {
  40. // repraesentiert Knoten und Heap geordnete Baeume
  41.  
  42. friend class f_heap;
  43.  
  44.    f_heap_node* next;          // used to link all used items 
  45.    int deleted;                // to mark deleted nodes
  46.  
  47.    f_heap_node* left;          // left and right siblings (circular List)
  48.    f_heap_node* right;   
  49.    f_heap_node* parent;        // parent node
  50.    f_heap_node* children;      // a child
  51.  
  52.    int rank;                   // number of children
  53.    int mark;                   // ( 1=true, 0=false )
  54.    ent key;                    // key
  55.    ent inf;                    // information
  56.  
  57.  
  58. // size: 9 words =  36 bytes
  59.  
  60.  
  61.    void link(f_heap_node*);
  62.    void cut(f_heap_node*);
  63.  
  64.  
  65. public:
  66.  
  67.    f_heap_node(ent k, ent info, f_heap_node* n) 
  68.    {  key = k;
  69.       inf = info;
  70.       next = n;
  71.       deleted = 0;
  72.       rank = 0;
  73.       mark = 0;
  74.       parent = 0;
  75.       children = 0;
  76.     }  // end of f_heap_node()
  77.  
  78. OPERATOR_NEW(10)
  79. OPERATOR_DEL(10)
  80.  
  81.  };  //f_heap_node
  82.  
  83.  
  84. typedef f_heap_node* f_heap_item;
  85.  
  86.  
  87. class f_heap
  88.  /* Ein F-Heap enthaelt eine zirkulaere Liste von Heap geordneten
  89.     Baeumen. Der Einstieg erfolgt ueber den minptr, einen Zeiger
  90.     auf den Baum mit kleinstem Schluessel in der Wurzel. Die ei-
  91.     gentlichen Items ( Paare aus /NxT ) sind in den Knoten der
  92.     Baeume enthalten.                                               */
  93.  { 
  94.    int node_count;         // number of nodes
  95.    f_heap_node* minptr;    // entry to the List of roots
  96.    f_heap_node* node_list; // List of all nodes
  97.  
  98.    f_heap_node** rank_field;
  99.  
  100.    int max_rank() const;
  101.  
  102.    f_heap_node* new_f_heap_node(ent k, ent i)
  103.    { return (node_list = new f_heap_node(k,i,node_list)); }
  104.  
  105.    virtual int cmp(ent& x, ent& y) const { return int(x)-int(y); }
  106.  
  107.    virtual void print_key(ent& x)  const { Print(x); }
  108.    virtual void print_inf(ent& x)  const { Print(x); }
  109.  
  110.    virtual void clear_key(ent& x)  const { Clear(x); }
  111.    virtual void clear_inf(ent& x)  const { Clear(x); }
  112.  
  113.    virtual void copy_key(ent& x)   const { Copy(x); }
  114.    virtual void copy_inf(ent& x)   const { Copy(x); }
  115.  
  116. public:
  117.  
  118.  f_heap();
  119.  f_heap(const f_heap&);
  120.  f_heap& operator=(const f_heap&);
  121. ~f_heap()  { clear(); delete rank_field; }
  122.  
  123.  
  124. f_heap_node* insert(ent, ent);
  125. f_heap_node* find_min() const { return(minptr); }
  126.  
  127. void del_min();  
  128. void decrease_key(f_heap_node*,ent);
  129. void change_inf(f_heap_node*,ent);
  130. void del_item(f_heap_node *x){ decrease_key(x,minptr->key); del_min();}
  131. void clear();
  132.  
  133. ent  key(f_heap_node *x) const { return x->key ; }
  134. ent  inf(f_heap_node *x) const { return x->inf; }
  135.  
  136.   
  137. int  size()  const { return node_count; }
  138. int  empty() const { return (find_min()==0) ? true : false; }
  139.  
  140.  
  141. // Iteration:
  142. f_heap_node* first_item() const;
  143. f_heap_node* next_item(f_heap_node*) const;
  144.  
  145.  
  146.  };  // end of class f_heap
  147.  
  148. #endif
  149.