tpl_dynArrayHeap.H

# ifndef TPL_DYNARRAYHEAP_H
# define TPL_DYNARRAYHEAP_H

# include <tpl_dynArray.H>

namespace Aleph {


    template <typename T, class Compare> inline
void sift_up(DynArray<T> & a, size_t l, size_t r)
{
  for (size_t p, i = r; i > l; i = p) 
    {
      p = u_index(i);
      T & ap = a.access(p);
      T & ai = a.access(i);
      if (Compare () (ap, ai)) // ¿cumple propiedad orden?
        return; // si, todo el arreglo es un heap

      std::swap(ap, ai); // intercambie y restaure nivel p
    }
}

    template <typename T, class Compare> inline
void sift_down(DynArray<T> & a, size_t l, size_t r)
{
  size_t i = l, c;
  while (true)
    {
      c = l_index(i); // índice del hijo izquierdo (c = i/2)
      if (c > r) // ¿hay hijo izquierdo?
        return; // no ==> termine

      T * ac = & a.access(c);
      if (c + 1 <= r) // ¿hay hijo derecho?
        {
          T * ac1 =  & a.access(c + 1);
          if (Compare () (*ac1, *ac)) // sí ==> escoja menor
            {
              c++;
              ac = ac1;
            }
        }

      T & ai = a.access(i);
      if (Compare () (ai, *ac)) // ¿cumple propiedad orden?
        return;  // sí ==> termine

      std::swap(*ac, ai); 
      i = c;
    }
}


    template <typename T, class Compare = Aleph::less<T>> 
class DynArrayHeap 
{
  DynArray<T> array;
  size_t      num_items;

  static size_t r_index(const size_t & i)
  {
    return (i << 1) + 1; // multiplica i por 2 y suma 1
  }

public:

  DynArrayHeap(Compare &) : num_items(0)
  { 
    // empty
  }

  DynArrayHeap(Compare && cmp = Compare()) : num_items(0)
  { 
    // empty
  }

  T & top() throw(std::exception, std::underflow_error)
  {
    if (num_items == 0)
      throw std::underflow_error("Heap is empty");

    return array.access(1);
  }

  T & insert(const T & key) throw(std::exception, std::overflow_error)
  {
    array.touch(++num_items) = key;  // colocar nuevo elemento
    sift_up<T,Compare>(array, 1, num_items); // restaurar propiedad orden
    return array.access(num_items);
  }

  T getMin() throw(std::exception, std::underflow_error)
  {
    if (num_items == 0)
      throw std::underflow_error("Heap is empty");

    T & a1 = array.access(1);
    T ret_val = a1;
    a1 = array[num_items--]; 
    sift_down<T,Compare>(array, 1, num_items); // propiedad orden

    array.cut(num_items + 1);

    return ret_val;
  }

  T get() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  T getMax() throw(std::exception, std::underflow_error)
  {
    return getMin();
  }

  const size_t & size() const { return num_items; }
  
  bool is_empty() const { return num_items == 0; }
};



} // end namespace Aleph

# endif // TPL_DYNARRAYHEAP_H