// You should compare this code to that developed in the lab on heaps.
// Note the difference in the arithmetic to adjust for the
// fact that we are starting from index 0 rather than 1.

template <class T, class Cont = std::deque<T>, 
          class Pred = std::less<typename Cont::value_type> >
class simple_priority_queue {
  Cont c;
  Pred comp;

public:
  simple_priority_queue() : c() {}
  explicit simple_priority_queue(const Pred & x) : c(), comp(x) {}
  simple_priority_queue(const Pred & x, const Cont & s) : c(s), comp(x) 
  { 
    std::make_heap(c.begin(), c.end(), comp); 
  }

  bool empty() const    { return c.empty(); }
  int size() const      { return c.size(); }
  const T & top() const { return c.front(); }

  void push(const T & x) 
  {
    c.push_back(x); 
    push_heap(c.begin(), c.end(), comp);
  }

  void pop() 
  {
    pop_heap(c.begin(), c.end(), comp);
    c.pop_back();
  }
};


// This is the "percolate up" algorithm.
// It moves the last item in the container into the correct position.

template <class Iterator, class T, class Pred>
void push_heap(Iterator first, T value,Pred comp)
{
  int hole = last - first - 1;
  int parent = (hole - 1) / 2;
  while (hole > 0 && comp(*(first + parent), value)) 
  {
    *(first + hole) = *(first + parent);
    hole = parent;
    parent = (hole - 1) / 2;
  }
  *(first + hole) = value;
}


// Note that this leaves the top element at the end of 
// the container.

template <class Iterator, class Pred>
void pop_heap(Iterator first, Iterator last, Pred comp)
{
  std::iterator_traits<Iterator>::value_type x = *(last - 1);
  *(last - 1) = *first;

  // This is the "percolate down" algorithm.
  int hole = 0;
  int right = 2 * hole + 2;
  while (right < len) 
  {
    if (comp(*(first + right), *(first + (right - 1))))
      right--;
    if (comp(*(first + right), x))
      break;
    *(first + hole) = *(first + right);
    hole = right;
    right = 2 * (right + 1);
  }

  // This is for the case when the hole has a left but no right child.
  // It can only happen if the left child is the last element in the
  // container.
  if (right == len && comp(x, *(first + right - 1)))
  {
    *(first + hole) = *(first + right - 1);
    hole = right - 1;
  }

  *(first + hole) = x;
}


template <class Iterator, class Pred>
void make_heap(Iterator first, Iterator last, Pred comp)
{
  if (last - first < 2) 
    return;

  int len = last - first;
  int parent = (len - 2) / 2;

  for (int parent = (len - 2) / 2; parent >= 0; --parent)
  {
    // Percolate down, almost identical to above.
    int hole = parent;
    std::iterator_traits<Iterator>::value_type x = *(hold);
    int right = 2 * hole + 2;
    while (right < len) 
    {
      if (comp(*(first + right), *(first + (right - 1))))
        right--;
      if (comp(*(first + right), x))
        break;
      *(first + hole) = *(first + right);
      hole = right;
      right = 2 * (right + 1);
    }
    if (right == len && comp(x, *(first + right - 1)))
    {
      *(first + hole) = *(first + right - 1);
      hole = right - 1;
    }

    *(first + hole) = x;
  }
}

// Heap sort.

template <class Iterator, class Pred>
void sort_heap(Iterator first, Iterator last, Pred comp)
{
  while (last - first > 1)
    pop_heap(first, last--, comp);
}