minmaxheap.hpp

Go to the documentation of this file.

#ifndef MINMAXHEAP_HPP
#define MINMAXHEAP_HPP

#include "vc6compat.h"

#include <algorithm>

struct compsmaller
{
    template< typename T1, typename T2 > 
    bool operator()( const T1& v1, const T2& v2 ) 
    { 
        return v1 < v2; 
    } 
};

struct compbigger
{
    template< typename T1, typename T2 > 
    bool operator()( const T1& v1, const T2& v2 ) 
    { 
        return v1 > v2; 
    } 
};

template <typename T, typename cmps, typename cmpb>
class minmaxheap {
  private:
    int size;
    int filled;
    T* heap;
    cmps s;
    cmpb b;
    void upheap(const int position);
    void downheap();
  public:
    minmaxheap(int size_) : size(size_), filled(0) { heap=new T[size]; }
    ~minmaxheap() { delete[] heap; }
    const T& operator[] (int n)  const { return heap[n]; }
    const T& operator() () const { return heap[0]; }
    void put (const T& elem);
    void clear() { filled=0; }  // fast delete content
};    


template <typename T, typename cmps, typename cmpb> 
void minmaxheap<T, cmps, cmpb>::upheap(const int position) {
  int sohn=position;
  int vater=sohn/2;
  while (sohn!=0) {
    if (b(heap[sohn],heap[vater])) return;
    std::swap(heap[sohn], heap[vater]);
    sohn=vater;
    vater=sohn/2;
  }  
}

template <typename T, typename cmps, typename cmpb> 
void minmaxheap<T, cmps, cmpb>::downheap() {
  int vater=0;
  int lsohn=2*vater+1;
  while (lsohn<filled) {
   if (s(heap[lsohn],heap[vater])) {
     if ((lsohn+1<filled) && (s(heap[lsohn+1],heap[lsohn]))) {
       // rechter Sohn existent und kleinster
       std::swap(heap[lsohn+1], heap[vater]);
       vater=lsohn+1;
     } else {
       // rechter Sohn nicht existent oder linker ist kleiner
       std::swap(heap[lsohn], heap[vater]);
       vater=lsohn;
     }
   } else {
     // linke Sohn nicht kleiner, rechter?
     if ((lsohn+1<filled) && (s(heap[lsohn+1],heap[vater]))) {
       // rechter Sohn existent und kleinster
       std::swap(heap[lsohn+1], heap[vater]);
       vater=lsohn+1;
     } else {
       return; 
       // Heap in Ordnung, kein Sohn kleiner als der Vater
     }
   }  
   lsohn=2*vater+1;
 }  
}


template <typename T, typename cmps, typename cmpb>
void minmaxheap<T, cmps, cmpb>::put(const T& elem) {
 
 if (filled<size) {
   // Aufbau des Heaps
   heap[filled]=elem;
   upheap(filled++);
 } else {
   // füge ein, falls größer als das kleinste Element
   if (b(elem,heap[0])) {
      heap[0]=elem;
      downheap();
   }
 }

}

template <typename T> 
class minheap: public minmaxheap<T, compsmaller, compbigger> {
  public:
    minheap(int size_) : minmaxheap<T, compsmaller, compbigger> (size_) { }
    const T& max() const { return minmaxheap<T, compsmaller, compbigger>::operator()(); }
};

template <typename T> 
class maxheap: public minmaxheap<T, compbigger, compsmaller> {
  public:
    maxheap(int size_) : minmaxheap<T, compbigger, compsmaller> (size_) { }
    const T& min() const { return minmaxheap<T, compbigger, compsmaller>::operator()(); }
};


#endif

---