Category

Development Platform
Home > SourceCode/Document > Mathimatics-Numerical algorithms > View Code
k_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

k_heap.h：Code Content
  1. /*******************************************************************************
  2. +
  3. +  LEDA-R  3.2.3
  4. +
  5. +  k_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_KHEAP_H
  14. #define LEDA_KHEAP_H
  16. //------------------------------------------------------------------------------
  17. // k-nary Heaps
  18. //------------------------------------------------------------------------------
  21. #include <LEDA/basic.h>
  23. class k_heap_elem
  24. {
  25.   friend class k_heap;
  27.   GenPtr key;
  28.   GenPtr inf;
  30.   int index;
  32.   k_heap_elem(GenPtr k, GenPtr i, int pos) { key = k; inf = i; index = pos; }
  34.   LEDA_MEMORY(k_heap_elem)
  36. };
  39. typedef k_heap_elem* k_heap_item;
  42. class k_heap  {
  44. virtual int cmp(GenPtr, GenPtr) const { return 0; }
  45. virtual void copy_key(GenPtr&)  const {}
  46. virtual void copy_inf(GenPtr&)  const {}
  47. virtual void clear_key(GenPtr&) const {}
  48. virtual void clear_inf(GenPtr&) const {}
  49. virtual void print_key(GenPtr)  const {}
  50. virtual void print_inf(GenPtr)  const {}
  52. virtual int  int_type() const { return 0; }
  55. int          K;
  56. int          count;
  57. int          max_size;
  58. k_heap_item* HEAP;
  60. void rise(int,k_heap_item);
  61. void sink(int,k_heap_item);
  63. void check(k_heap_item);
  65. protected:
  67. k_heap_item item(GenPtr p) const { return k_heap_item(p); }
  69. public:
  71. k_heap_item insert(GenPtr, GenPtr);
  72. k_heap_item find_min()  const      { return HEAP[1];  }
  73. k_heap_item first_item() const     { return HEAP[1]; }
  74. k_heap_item next_item(k_heap_item it) const { return HEAP[it->index+1];}
  76. void decrease_key(k_heap_item, GenPtr);
  77. void change_inf(k_heap_item, GenPtr);
  78. void del_item(k_heap_item);
  79. void del_min() { del_item(find_min()); }
  81. GenPtr key(k_heap_item it) const { return it->key; }
  82. GenPtr inf(k_heap_item it) const { return it->inf; }
  84. int  size()    const  { return count;    }
  85. bool empty()   const  { return count==0; }
  87. void clear();
  88. void print();
  90. k_heap& operator=(const k_heap&);
  92. k_heap(int n=0,int k=2);  // default: binary heap
  93. k_heap(const k_heap&);
  95. virtual ~k_heap();
  97. };
  99. #endif