开通博客赚积分
发布资源赚积分
分类

源码开发语言/平台
当前位置：首页 > 源码/资料 > 数值算法/人工智能 > 查看源码
f_heap.h
资源名称：leda.tar.gz　[点击查看]
上传用户：gzelex
上传日期：2007-01-07
资源大小：707k
文件大小：4k
源码类别：

数值算法/人工智能

开发平台：

MultiPlatform

f_heap.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  f_heap.h
  6. +
  7. +  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
  8. +  Im Stadtwald, 66123 Saarbruecken, Germany     
  9. +  All rights reserved.
  10. + 
  11. *******************************************************************************/
  14. #ifndef LEDA_FHEAP_H
  15. #define LEDA_FHEAP_H
  17. //------------------------------------------------------------------------------
  18. //
  19. // Fibonacci Heap
  20. //
  21. // Michael Muth  (1988)
  22. //
  23. // Modifications
  24. //
  25. // - virtual compare function  (Stefan Naeher, August 1989)
  26. //
  27. // - virtual clear functions   (Stefan Naeher, April 1990)
  28. //
  29. //------------------------------------------------------------------------------
  32. #include <LEDA/basic.h>
  35. class f_heap_node  {
  36. // repraesentiert Knoten und Heap geordnete Baeume
  38. friend class f_heap;
  40.    f_heap_node* next;          // used to link all used items 
  41.    f_heap_node* pred;          
  43.    f_heap_node* left;          // left and right siblings (circular List)
  44.    f_heap_node* right;   
  45.    f_heap_node* parent;        // parent node
  46.    f_heap_node* children;      // a child
  48.    int  rank;                   // number of children
  49.    char mark;                   // ( 1=true, 0=false )
  51.    GenPtr key;                  // key
  52.    GenPtr inf;                  // information
  55. // size: 10 words =  40 bytes
  58.    void link(f_heap_node*);
  59.    void cut(f_heap_node*);
  62. public:
  64.    f_heap_node(GenPtr k, GenPtr i, f_heap_node* n) 
  65.    {  key = k;
  66.       inf = i;
  67.       next = n;
  68.       pred = 0;
  69.       rank = 0;
  70.       mark = 0;
  71.       parent = 0;
  72.       children = 0;
  74.       if (n) n->pred = this;
  76.     }  // end of f_heap_node()
  79.   LEDA_MEMORY(f_heap_node)
  81.  };  //f_heap_node
  84. typedef f_heap_node* f_heap_item;
  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
  98.    int max_rank() const;
  100.    f_heap_node* new_f_heap_node(GenPtr k, GenPtr i)
  101.    { return  node_list = new f_heap_node(k,i,node_list); }
  103.    virtual int cmp(GenPtr, GenPtr) const { return 0; }
  105.    virtual void print_key(GenPtr)  const {}
  106.    virtual void print_inf(GenPtr)  const {}
  108.    virtual void clear_key(GenPtr&) const {}
  109.    virtual void clear_inf(GenPtr&) const {}
  111.    virtual void copy_key(GenPtr&)  const {}
  112.    virtual void copy_inf(GenPtr&)  const {}
  114.    virtual int  int_type() const { return 0; }
  116. protected:
  118.   f_heap_node* item(void* p) const { return (f_heap_node*)p; }
  120. public:
  122.  f_heap();
  123.  f_heap(const f_heap&);
  124.  f_heap& operator=(const f_heap&);
  126. virtual ~f_heap()  { clear(); }
  129. f_heap_node* insert(GenPtr, GenPtr);
  130. f_heap_node* find_min() const { return(minptr); }
  132. void del_min();  
  133. void decrease_key(f_heap_node*,GenPtr);
  134. void change_inf(f_heap_node*,GenPtr);
  135. void del_item(f_heap_node *x){ decrease_key(x,minptr->key); del_min();}
  136. void clear();
  138. GenPtr  key(f_heap_node *x) const { return x->key ; }
  139. GenPtr  inf(f_heap_node *x) const { return x->inf; }
  141.   
  142. int  size()  const { return node_count; }
  143. int  empty() const { return (find_min()==0) ? true : false; }
  146. // Iteration:
  149. f_heap_node* first_item() const;
  151. f_heap_node* next_item(f_heap_node* p) const;
  155. };  // end of class f_heap
  158. // dummy I/O and cmp functions
  160. inline void Print(const f_heap&, ostream&) { }
  161. inline void Read (f_heap&, istream&) { }
  162. inline int  compare(const f_heap&,const f_heap&) { return 0; }
  164. #endif