m_heap.h

高效数据类型和算法库

/*******************************************************************************
+
+  LEDA-R  3.2.3
+
+  m_heap.h
+
+  Copyright (c) 1995  by  Max-Planck-Institut fuer Informatik
+  Im Stadtwald, 66123 Saarbruecken, Germany     
+  All rights reserved.
+ 
*******************************************************************************/

#ifndef LEDA_M_HEAP_H
#define LEDA_M_HEAP_H

//------------------------------------------------------------------------------
// m_heap : monotonic heaps 
//
// a) the sequence of minimum keys (over time) is monotonic (non-decreasing)
// b) the difference of minimum and maximum key is bounded by a constant M
//
// Implementation: cyclic array of lists
//
// Stefan Naeher  (1991)
//------------------------------------------------------------------------------


#include <LEDA/basic.h>
#include <LEDA/list.h>


typedef list_item m_heap_item;

class m_heap {

    int start;
    int offset;
    int M;
    int count;
    list<GenPtr> L;

    list_item*   T;

virtual void copy_inf(GenPtr&)  const {}
virtual void clear_inf(GenPtr&) const {}
virtual void print_inf(GenPtr x) const { cout << x; }

protected:

m_heap_item item(void* p) const { return (m_heap_item)p; }

public:

m_heap_item insert(GenPtr,GenPtr);
m_heap_item find_min() const;
m_heap_item first_item() const;
m_heap_item next_item(m_heap_item) const;

GenPtr       del_min();

void change_key(m_heap_item,GenPtr);
void decrease_key(m_heap_item it,GenPtr x) { change_key(it,x); }
void change_inf(m_heap_item it, GenPtr x)  { copy_inf(x); L[it] = x; };
void del_item(m_heap_item);
void clear();

GenPtr inf(m_heap_item it) const { return L.inf(it); }

GenPtr key(m_heap_item) const
{ error_handler(1,"m_heap::key not implemented");
  return 0; 
 }

int    size()   const     { return count; }
int    empty()  const     { return count==0; }

void   print() const;

 m_heap(int M=1024);         
 m_heap(int,int) { error_handler(1,"illegal constuctor"); }

virtual ~m_heap() { delete T; }


// still to do: copy operations

 m_heap& operator=(const m_heap&) { return *this; }
 m_heap(const m_heap&) {}

};

#endif