\section{heap.H}

<<heap.H>>=

#include <string.h>

template<class T> inline bool less(const T& a, const T& b) {
  return (a < b);
}

inline bool less(const char* a, const char* b) {
  return (strcmp(a, b) < 0 ? true : false);
}

template<class T> inline void swap(T& a, T& b) {
  T temp(a);
  a = b;
  b = temp;
}

template<class T> class heap {
private:
  size_t size;
  size_t length;
  T* a;

public:
  heap(size_t initial_size = 10):
    size(initial_size),
    length(0),
    a(new T[initial_size])
  { }

  heap(T array[], size_t nUsed):a(array), size(sizeof(array)), length(nUsed)
  { }
  
  virtual ~heap() {
    delete[] a;
  }
  
  size_t get_used() {
    return length;
  }
  
  bool is_empty() {
    return (length == 0);
  }
  
  T min() {
    if (is_empty()) {
      throw(3);
    }
    return a[0];
  }
  
  void del_min() {
    a[0] = a[length - 1];
    --length;
    movedown(0);
  }

  void movedown(size_t pos) {
    T moving_elem = a[pos];
    size_t iSon, iSonDx;

    for(;;) {
      iSon = (pos << 1) + 1;
      if((iSonDx = iSon + 1) < length && less(a[iSonDx], a[iSon]))
        ++iSon;
      if(iSon < length && less(a[iSon], moving_elem)) {
        a[pos] = a[iSon];
        pos = iSon;
      }
      else {
        a[pos] = moving_elem;
        return;
      }
    }     
  }
  
  void insert(const T& elem) {
    if (length == size) {
      size_t newsize = size * 2 + 1;
      T* b = new T[newsize];
      memcpy((void*)a, (void*)b, sizeof(T)*size);
      swap(a, b);
      size = newsize;
      delete[] b;
    }
    
    a[length] = elem;
    
    moveup(length);
        
    ++length;
  }
  
  void moveup(size_t pos) {
    T moving_elem = a[pos];
    int father;

    while((father = (int)(pos - 1) >> 1) >= 0 && less(moving_elem, a[father])) {    
      a[pos] = a[father];
      pos = father;
    }

    a[pos] = moving_elem;
  }

  void touch(size_t pos) {
    if(pos > 0 && pos < length && less(a[pos], a[(pos - 1) >> 1]))
      moveup(pos);
    else
      movedown(pos);
  }
};
@