Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
bin_heap.h
Package: leda.tar.gz　[view]
Upload User: gzelex
Upload Date: 2007-01-07
Package Size: 707k
Code Size: 2k
Category:

Mathimatics-Numerical algorithms

Development Platform:

MultiPlatform

bin_heap.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  bin_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_BIN_HEAP_H
  14. #define LEDA_BIN_HEAP_H
  16. //------------------------------------------------------------------------------
  17. // binary Heaps
  18. //
  19. // S. Naeher (1993)
  20. //
  21. //------------------------------------------------------------------------------
  24. #include <LEDA/basic.h>
  27. class bin_heap_elem
  28. {
  29.   friend class bin_heap;
  31.   GenPtr key;
  32.   GenPtr inf;
  34.   int index;
  36.   bin_heap_elem(GenPtr k, GenPtr i, int pos) { key = k; inf = i; index = pos; }
  38.   LEDA_MEMORY(bin_heap_elem)
  40. };
  43. typedef bin_heap_elem* bin_heap_item;
  46. class bin_heap  {
  48. virtual int  cmp(GenPtr, GenPtr) const { return 0; }
  49. virtual void copy_key(GenPtr&)   const {}
  50. virtual void copy_inf(GenPtr&)   const {}
  51. virtual void clear_key(GenPtr&)  const {}
  52. virtual void clear_inf(GenPtr&)  const {}
  53. virtual void print_key(GenPtr)   const {}
  54. virtual void print_inf(GenPtr)   const {}
  56. virtual int  int_type() const { return 0; }
  59. int          count;
  60. int          max_size;
  62. bin_heap_item* HEAP;
  65. void rise(int,bin_heap_item);
  66. void sink(int,bin_heap_item);
  68. protected:
  70. bin_heap_item item(GenPtr p) const { return bin_heap_item(p); }
  72. public:
  74. bin_heap_item insert(GenPtr, GenPtr);
  75. bin_heap_item find_min()  const      { return HEAP[1];  }
  76. bin_heap_item first_item() const     { return HEAP[1]; }
  77. bin_heap_item next_item(bin_heap_item it) const { return HEAP[it->index+1];}
  79. void decrease_key(bin_heap_item, GenPtr);
  80. void change_inf(bin_heap_item, GenPtr);
  81. void del_item(bin_heap_item);
  82. void del_min() { del_item(find_min()); }
  84. GenPtr key(bin_heap_item it) const { return it->key; }
  85. GenPtr inf(bin_heap_item it) const { return it->inf; }
  87. int  size()    const  { return count;    }
  88. bool empty()   const  { return count==0; }
  90. void clear();
  91. void print();
  93. bin_heap& operator=(const bin_heap&);
  95. bin_heap(int n = 1024);  // default start size 
  96. bin_heap(const bin_heap&);
  98. bin_heap(int,int) {}
  100. virtual ~bin_heap();
  102. };
  104. #endif