C++でpriority_queueを実装する

(競プロ以外の場面で)優先度付きキューを自力で実装する必要に迫られたので、自力で実装してみました。二分ヒープをベースに実装してあります。

※いくつかのメソッドは実装していません

実装

#include <vector>
#include <functional>

template <class T,
         class Container = std::vector<T>,
         class Compare = std::less<typename Container::value_type>>
         class priority_queue
{
  Container v;
  int size = 0;
  public:
  void push(T val) {
    int index = size;
    v.push_back(val);
    ++size;

    for (int parent = (index-1) / 2;
        parent >= 0 && Compare()(v[parent], v[index]);
        index = parent, parent = (index-1)/2) {
      T tmp = v[index];
      v[index] = v[parent];
      v[parent] = tmp;
    }
  }
  void pop() {
    v[0] = v[size-1];
    v.pop_back();
    --size;

    for (int index = 0, l = 1, r = 2;
        l < size && (Compare()(v[index], v[l]) || Compare()(v[index], v[r]));
        l = index * 2 + 1, r = index * 2 + 2) {
      int target = l;
      if (Compare()(v[index], v[r])) target = r;
      if (Compare()(v[index], v[l]) && Compare()(v[index], v[r]))
        if (Compare()(v[r], v[l])) target = l;
        else target = r;

      T tmp = v[index];
      v[index] = v[target];
      v[target] = tmp;
      index = target;
    }
  }
  T top() { return v.front(); }
  bool empty() { return size == 0; }
};