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

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

数值算法/人工智能

开发平台：

MultiPlatform

p_heap.h：源码内容
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  p_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. *******************************************************************************/
  13. #ifndef LEDA_PAIRING_HEAP_H
  14. #define LEDA_PAIRING_HEAP_H
  16. #include<LEDA/basic.h>
  18. // Implementation following John T. Stasko and Jeffrey Scott Vitter
  19. // ( Communications of the ACM   March 1987 Volume 30 Number 3   S. 234-240 )
  20. //
  21. // by Markus Neukirch   (1992)
  23. class ph_item
  24. {
  25.   friend class pairing_heap;
  26.   friend class p_heap;
  27.   friend class p_aux_heap;
  29.         GenPtr key;
  30.         GenPtr inf;
  32.         ph_item* parent;
  33.         ph_item* l_child;
  34.         ph_item* r_child;
  37.         ph_item(GenPtr k,GenPtr i)
  38.         { parent = l_child = r_child=nil;
  39.           key=k;
  40.           inf=i;
  41.          }
  43.        ~ph_item()       {} 
  44.         
  45.   LEDA_MEMORY(ph_item)
  46.         
  47. };
  50. class p_heap
  51. {
  52.         
  53.         ph_item* head;
  54.         int item_count;
  55.         void do_copy(ph_item*,ph_item*,bool);
  56.         void copy_sub_tree(ph_item*, ph_item*);
  57.         void clear_sub_tree(ph_item*);
  58.         ph_item* new_ph_item(GenPtr,GenPtr);
  60.         virtual int cmp(GenPtr, GenPtr) const {return 0; }
  61.         virtual void print_key(GenPtr)  const {}
  62.         virtual void print_inf(GenPtr)  const {}
  63.         virtual void clear_key(GenPtr&) const {}
  64.         virtual void clear_inf(GenPtr&) const {}
  65.         virtual void copy_key(GenPtr&)  const {}
  66.         virtual void copy_inf(GenPtr&)  const {}
  67.  
  68.         virtual int  int_type() const { return 0; }
  69.  
  70. protected:
  72.         //ph_item* comparison_link(ph_item*,ph_item*);
  74.         ph_item* twopass(ph_item*);
  75.         ph_item* multipass(ph_item*);
  77.         ph_item* item(void* p) const { return (ph_item*)p; }
  79.         
  80. public:
  81.         p_heap()        { item_count=0; }
  83.         p_heap(int)     { error_handler(1,"no p_heap(int) constructor");}
  84.         p_heap(int,int) { error_handler(1,"no p_heap(int,int) constructor");}
  86.         p_heap(const p_heap&);
  87.         p_heap& operator=(const p_heap&);
  89. virtual ~p_heap() { clear(); }
  92.         ph_item* insert(GenPtr,GenPtr);
  94.         ph_item* find_min() const { return head; }
  96.         void decrease_key(ph_item*,GenPtr);
  97.         void delete_min_multipass();
  98.         void delete_min_twopass();
  100.         void del_min() { delete_min_twopass(); }
  102.         GenPtr key(ph_item* x) const {return x->key;}
  103.         GenPtr inf(ph_item* x) const {return x->inf;}
  106.         void change_inf(ph_item* x,GenPtr inf)
  107.                 {clear_inf(x->inf);copy_inf(inf);x->inf=inf;}
  108.         void del_item(ph_item* x)
  109.                 {decrease_key(x,head->key);delete_min_twopass();}
  111.         void clear ();
  112.         
  113.         int  size() const  { return item_count; }
  114.         int  empty() const { return item_count>0; }
  116.         // iteration (not yet implemented)
  118.         ph_item* first_item()        const { return 0; }
  119.         ph_item* next_item(ph_item*) const { return 0; }
  121. };      
  123. #endif