/*******************************************************************************++  LEDA 3.5+++  bin_heap.h+++  Copyright (c) 1995, 1996, 1997  by  LEDA Software GmbH+  Postfach 151101, 66041 Saarbruecken, Germany+  All rights reserved.+ *******************************************************************************/#ifndef LEDA_BIN_HEAP_H#define LEDA_BIN_HEAP_H//------------------------------------------------------------------------------// binary Heaps//// S. Naeher (1993)////------------------------------------------------------------------------------#include <LEDA/basic.h>class __exportC bin_heap_elem{  friend class __exportC bin_heap;  GenPtr key;  GenPtr inf;  int index;  bin_heap_elem(GenPtr k, GenPtr i, int pos) { key = k; inf = i; index = pos; }  LEDA_MEMORY(bin_heap_elem)};typedef bin_heap_elem* bin_heap_item;class __exportC bin_heap  {virtual int  cmp(GenPtr, GenPtr) const { return 0; }virtual void copy_key(GenPtr&)   const {}virtual void copy_inf(GenPtr&)   const {}virtual void clear_key(GenPtr&)  const {}virtual void clear_inf(GenPtr&)  const {}virtual void print_key(GenPtr)   const {}virtual void print_inf(GenPtr)   const {}virtual int  key_type_id() const { return UNKNOWN_TYPE_ID; }int          count;int          max_size;bin_heap_item* HEAP;void rise(int,bin_heap_item);void gen_rise(int,bin_heap_item);void int_rise(int,bin_heap_item);void double_rise(int,bin_heap_item);void sink(int,bin_heap_item);void gen_sink(int,bin_heap_item);void int_sink(int,bin_heap_item);void double_sink(int,bin_heap_item);public:typedef bin_heap_item item;bin_heap_item insert(GenPtr, GenPtr);bin_heap_item find_min()  const      { return HEAP[1];  }bin_heap_item first_item() const     { return HEAP[1]; }bin_heap_item next_item(bin_heap_item it) const { return it ? HEAP[it->index+1] : 0;}void decrease_key(bin_heap_item, GenPtr);void change_inf(bin_heap_item, GenPtr);void del_item(bin_heap_item);void del_min() { del_item(find_min()); }GenPtr key(bin_heap_item it) const { return it->key; }GenPtr inf(bin_heap_item it) const { return it->inf; }int  size()    const  { return count;    }bool empty()   const  { return count==0; }void clear();void print();bin_heap& operator=(const bin_heap&);bin_heap(int n = 1024);  // default start size bin_heap(const bin_heap&);bin_heap(int,int) {}virtual ~bin_heap();};#endif