priority_queue<int, vector<int>,less<int> > q1;

priority_queue<int, vector<int>> q2;

priority_queue<int> q3;

void test_priority_queue()
{
  priority_queue<int, vector<int>, less<int> > q1;
  q1.push(1);
  q1.push(4);
  q1.push(9);
  q1.push(3);
  q1.push(7);
  while (!q1.empty())
  {
  cout << q1.top() << endl;
  q1.pop();
  }
}

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) 
    {
        // 我们使用优先级队列来做
        // 因为要求第k大的数字  所以说我们只要建立一个大堆
        // 然后pop掉前面k-1个数字 最后的一个数字就是我们要求的了
        priority_queue<int> q1;
        for (auto x : nums)
        {
            q1.push(x);
        }
        // 之后删掉前面k-1个数 就是第k大个数在最前面了
        while(k-1)
        {
            q1.pop();
            k--;
        }
        return q1.top();
    }
};

void adjust_up(vector<int>& v ,int child)
{
  // 首先找出孩子的父节点
  int father = (child - 1) / 2;
  // 当子节点不为根节点时就一直判断
  while ( child > 0 )
  {
  if (v[child] > v[father])
  {
    swap(v[child], v[father]);
    child = father;
    father = (child - 1) / 2;
  }
  else
  {
    // 符合规则 直接跳出循环
    break;
  }
  }
}

void adjust_down(vector<int>& v, int father)
{
  int child = 2 * father + 1;//左孩子
  // 开始循环 直到父亲没有孩子 或者符合小堆结构位置
  while (child < v.size())
  {
  // 首先判断右孩子是否存在并且右孩子是否大于左孩子
  // 因为要是比较大的那个做父亲
  if (child + 1 < v.size() && v[child+1] > v[child])
  {
    child++;
  }
  // 之后就判断 孩子是否大于父亲 如果大于就交换并且继续比较 如果不大于就结束
  if (v[child] > v[father])
  {
    swap(v[child], v[father]);
    father = child;
    child = 2 * father + 1;
  }
  else
  {
    break;
  }
  }
}

struct Less
{
  template<class T>
  bool operator() (T& x, T& y)
  {
  return x < y;
  }
};

struct Greater
{
  template<class T>
  bool operator() (T& x, T& y)
  {
  return x > y;
  }
};

priority_queue模拟实现
namespace shy //防止命名冲突
{
  //比较方式（使内部结构为大堆）
  template<class T>
  struct less
  {
  bool operator()(const T& x, const T& y)
  {
    return x < y;
  }
  };
  //比较方式（使内部结构为小堆）
  template<class T>
  struct greater
  {
  bool operator()(const T& x, const T& y)
  {
    return x > y;
  }
  };
  //优先级队列的模拟实现
  template<class T, class Container = vector<T>, class Compare = less<T>>
  class priority_queue
  {
  public:
  //堆的向上调整
  void AdjustUp(int child)
  {
    int parent = (child - 1) / 2; //通过child计算parent的下标
    while (child > 0)//调整到根结点的位置截止
    {
    if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
    {
      //将父结点与孩子结点交换
      swap(_con[child], _con[parent]);
      //继续向上进行调整
      child = parent;
      parent = (child - 1) / 2;
    }
    else//已成堆
    {
      break;
    }
    }
  }
  //插入元素到队尾（并排序）
  void push(const T& x)
  {
    _con.push_back(x);
    AdjustUp(_con.size() - 1); //将最后一个元素进行一次向上调整
  }
  //堆的向下调整
  void AdjustDown(int n, int parent)
  {
    int child = 2 * parent + 1;
    while (child < n)
    {
    if (child + 1 < n&&_comp(_con[child], _con[child + 1]))
    {
      child++;
    }
    if (_comp(_con[parent], _con[child]))//通过所给比较方式确定是否需要交换结点位置
    {
      //将父结点与孩子结点交换
      swap(_con[child], _con[parent]);
      //继续向下进行调整
      parent = child;
      child = 2 * parent + 1;
    }
    else//已成堆
    {
      break;
    }
    }
  }
  //弹出队头元素（堆顶元素）
  void pop()
  {
    swap(_con[0], _con[_con.size() - 1]);
    _con.pop_back();
    AdjustDown(_con.size(), 0); //将第0个元素进行一次向下调整
  }
  //访问队头元素（堆顶元素）
  T& top()
  {
    return _con[0];
  }
  const T& top() const
  {
    return _con[0];
  }
  //获取队列中有效元素个数
  size_t size() const
  {
    return _con.size();
  }
  //判断队列是否为空
  bool empty() const
  {
    return _con.empty();
  }
  private:
  Container _con; //底层容器
  Compare _comp; //比较方式
  };
}