#include<iostream>
#include<queue>
#include<vector>
using namespace std;
//要明白，此时的堆是一个数组（容器适配器默认是vector），就是使用数组的形式，给我们弄成了一个树的结构，就叫堆
namespace wwx
{
  template<class T>
  struct less//小堆仿函数
  {
    bool operator()(const T& x, const T& y)
    {
      return x < y;
    }
  };
  template<class T, class Container = vector<T>>//建大堆，我们用小于
  struct greater//大堆仿函数
  {
    bool operator()(const T& x, const T& y)
    {
      return x > y;
    }
  };
  template<class T, class Container = vector<T>, class Compare = greater<T>>//此时就可以不需要使用函数指针来调用某个函数了，可以直接使用模板类型来调用仿函数
  class priority_queue
  {
  public:
    void adjust_up(int child)
    {
      int parent = (child - 1) / 2;//这边一定要去把堆排序给复习一下（这个是可以自己推出来的）
      while (child > 0)//建大堆，最坏的情况就是当child为根结点的时候（也就是下标为0的时候），当下标为0就可以停下来了（不然它是会自己break出去的）
      {
        Compare com;
        //if (_con[parent] < _con[child])//建大堆
        if (com(_con[parent], _con[child]))//调用仿函数去比较
        {
          std::swap(_con[parent], _con[child]);
          child = parent;//建大堆（孩子结点大，此时就是让孩子变成父亲，然后重复再去寻找它的父结点）
          parent = (child - 1) / 2;//迭代走走
        }
        else
        {
          break;//此时此时只是向上调整，并不是堆排序
        }
      }
    }
    void adjust_down(int parent)//注意，此时是在类和对象中，所以可以直接使用this指针，所以可以直接使用我们的适配器来存储数据
    {
      int child = parent * 2 + 1;//父亲结点是唯一的，但是孩子结点是有两个
      while (child < _con.size())//这个条件不会写，就是把this指针给漏掉了
      {
        Compare com;
        //if (child + 1 < _con.size() && _con[child] < _con[child + 1])//左孩子小于右孩子（但是前提是右孩子存在，因为有的地方右孩子是不存在的），所以又漏了一个条件
        if (child + 1 < _con.size() && com(_con[child], _con[child + 1]))
        //if (child + 1 < _con.size() && Compare()(_con[child], _con[child + 1]))//使用匿名对象的写法
        {
          child += 1;
        }
        //if (_con[parent] < _con[child])//但是这种写法是有一个前提的（那种没有前提的写法要去复习）
        if (com(_con[parent], _con[child]))
        {
          std::swap(_con[parent], _con[child]);
          parent = child;
          child = parent * 2 + 1;//迭代
        }
        else
        {
          break;
        }                                  
      }
    }
    //总结：写这种代码，就是要把堆的结构给深深的烙印在脑海里面（树状结构）
    void push(const T& x)
    {
      _con.push_back(x);
      adjust_up(_con.size() - 1);//尾插数据之后，建堆，通过向上调整的形式
    }
    void pop()//上述是堆的插入，现在是堆的删除
    {//这边可以刚好去把堆排序给复习一下
      std::swap(_con[0], _con[_con.size() - 1]);
      _con.pop_back();
      adjust_down(0);
    }
    const T& top()
    {
      return _con[0];
    }
    size_t size()
    {
      return _con.size();
    }
    bool empty()
    {
      return _con.empty();
    }
  private:
    Container _con;
  };
  void test_priority_queue()
  {
    priority_queue<int> pq;
    pq.push(1);
    pq.push(2);
    pq.push(3);
    pq.push(4);
    pq.push(5);
    while (!pq.empty())
    {
      cout << pq.top() << " ";
      pq.pop();
    }
    cout << endl;
  }
}
int main()
{
  wwx::test_priority_queue();
  return 0;
}