C++编程：实战教程 - 实现栈与队列(Deque) 容器适配器，探讨Stack和Queue的实现及Queueue（Deque）的问题。深入理解：如何模拟实现Priority Queue (优先级队列) - 实例与练习。续集：仿函数在C++中的二次探索

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int>  pq(nums.begin(),nums.end());
       while(--k)
       {
           pq.pop();
       }
       return pq.top();
    }
};

namespace myspace
{
  //大堆
  template<class T,class Container=vector<T>>
  class priority_queque
  {
  public:
  template<class InputerIterator>
  priority_queque(InputerIterator first, InputerIterator last)//迭代器区间
  {
    while (first < last)
    {
    _con.push_back(*first);
    ++first;
    }
    //建堆
    for (int i = (_con.size() - 1 - 1)/2;i>=0;--i)
    {
    adjust_down(i);
     }
  }priority_queque()//默认构造，不然会报错，因为上面的迭代器区间这个函数跟构造函数同名
  {}
  void adjust_up(size_t child)
  {
    size_t parent = (child - 1) / 2;
    while (child>0)
    {
    if (_con[parent] < _con[child])
    {
      std::swap(_con[parent], _con[child]);
      child = parent;
      parent = (child - 1) / 2;
    }
    else
    {
      break;
    }
    }
  }
  void adjust_down(size_t parent)
  {
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
    if (child + 1 < _con.size() && _con[child + 1] > _con[child])
    {
      ++child;
    } //选出最大的孩子
    if (_con[child] > _con[parent])
    {
      std::swap(_con[child],_con[parent]);
      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];
  }
  bool empty()
  {
    return _con.empty();
  }
  size_t size()const
  {
    return _con.size();
  }
  private:
  Container _con;
  };
}
int main()
{
  int a[]= { 156,132,156,156,31,5,15,31,364,15 };
  myspace::priority_queque<int> pq(a,a+sizeof(a)/sizeof(int));
  while (!pq.empty())
  {
  cout << pq.top() << " ";
  pq.pop();
  }
  return 0;
}

namespace myspace
{
  template<class T>
  class less
  {
  public:
  bool operator()(const T& l, const T& r)const
  {
    return l < r;
  }
  };
  template<class T>
  class greater
  {
  public:
  bool operator()(const T& l, const T& r)const
  {
    return l > r;
  }
  };
}