bin_heap.h

A Library of Efficient Data Types and Algorithms,封装了常用的ADT及其相关算法的软件包

/*******************************************************************************
+
+  LEDA 4.5  
+
+
+  bin_heap.h
+
+
+  Copyright (c) 1995-2004
+  by Algorithmic Solutions Software GmbH
+  All rights reserved.
+ 
*******************************************************************************/

// $Revision: 1.3 $  $Date: 2004/02/06 11:18:50 $

#ifndef LEDA_BIN_HEAP_H
#define LEDA_BIN_HEAP_H

//------------------------------------------------------------------------------
// binary Heaps
//
// S. Naeher (1993)
//
//------------------------------------------------------------------------------


#include <LEDA/basic.h>

LEDA_BEGIN_NAMESPACE


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 && it->index < count) ? HEAP[it->index+1] : 0;}

bin_heap_item last_item() const { return 0; }

bin_heap_item stl_pred_item(bin_heap_item) const 
{  error_handler(1,"bin_heap::stl_pred_item not implemented."); return 0; }

bin_heap_item stl_next_item(bin_heap_item it) const 
{ return (it && it->index < count) ? HEAP[it->index+1] : HEAP[1]; }


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()); }

const 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();

};

LEDA_END_NAMESPACE

#endif