Re: STL Container?

Am 02.05.12 17:07, schrieb Marcel M??ller:


This can be done by heapsort. You can freely use the following (older)
implementation done by me (not an STL compliant container, though)

minmaxheap.hpp:

#ifndef MINMAXHEAP_HPP
#define MINMAXHEAP_HPP

#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

Test:
#include <iostream>
#include "minmaxheap.hpp"

int main() {

   int test[10] = { 1,9,2,28,30,10,6,8,9,28 };
   for (int i=1; i<=10; i++) {
     minheap<int> nmax(i);
     for (int k=0; k<10; k++) nmax.put(test[k]);
     for (int k=0; k<i; k++) std::cout<<nmax[k]<<" ";
     std::cout<<std::endl;
     std::cout<<"Maximum: "<<nmax.max()<<" ";
   }
   for (int i=1; i<=10; i++) {
     maxheap<int> nmax(i);
     for (int k=0; k<10; k++) nmax.put(test[k]);
     for (int k=0; k<i; k++) std::cout<<nmax[k]<<" ";
     std::cout<<std::endl;
      std::cout<<"Minimum: "<<nmax()<<" ";
   }
   return 0;
}

PS: I remember you use VC6 - use this definition to repair for scoping

#define for if(0);else for