函数声明	接口说明
priority_queue()/priority_queue(first,last)	构造一个空的优先级队列
empty( )	检测优先级队列是否为空，是返回true，否则返回 false
top( )	返回优先级队列中最大(最小元素)，即堆顶元素
push(x)	在优先级队列中插入元素x
pop()	删除优先级队列中最大(最小)元素，即堆顶元素

测试：

#include<queue>
#include<iostream>
using namespace std;
int main()
{
  //够一个空的优先级队列
  priority_queue<int> pri_q;
  //插入数据
  pri_q.push(2);
  pri_q.push(27);
  pri_q.push(25);
  pri_q.push(244);
  pri_q.push(212);
  pri_q.push(9);
  //连续取出堆顶数据打印
  while (!pri_q.empty())
  {
    cout << pri_q.top()<<' ';
    pri_q.pop();
  }
  return 0;
}

编辑

三.仿函数

如果我们像控制优先级队列是大堆排，还是小堆排，就需要我们使用放仿函数去控制。

1.什么是仿函数

首先仿函数是一个类，它重载了括号运算符，在使用的时候，定义出对象，就像函数一样使用。

例如：

//仿函数
template<class T>
struct Add
{
  int operator()(int e1, int e2)
  {
    return e1 + e2;
  }
};
int main()
{
  Add<int> add;
  cout << add(10, 20) << endl;
  return 0;
}

编辑

2.控制大小堆

在头文件<functional>中包含了两个仿函数,less和granter。

less是判断小于的仿函数，对应堆排出来是大堆，granter是判断大于的仿函数，对应堆排出来是小堆。

#include<queue>
#include<functional>
#include<iostream>
using namespace std;
int main()
{
  //小堆
  priority_queue<int,vector<int>,greater<int>> small_q;
  //插入数据
  small_q.push(2);
  small_q.push(27);
  small_q.push(25);
  small_q.push(244);
  small_q.push(212);
  small_q.push(9);
  //连续取出堆顶数据打印
  while (!small_q.empty())
  {
    cout << small_q.top()<<' ';
    small_q.pop();
  }
  cout  << endl;
  //大堆
  priority_queue<int, vector<int>, less<int>> big_q;
  //插入数据
  big_q.push(2);
  big_q.push(27);
  big_q.push(25);
  big_q.push(244);
  big_q.push(212);
  big_q.push(9);
  //连续取出堆顶数据打印
  while (!big_q.empty())
  {
    cout << big_q.top() << ' ';
    big_q.pop();
  }
  return 0;
}

编辑

3.TopK问题

这个问题我们在数据结构二叉树堆的部分已经详细的分析了，感兴趣的可以去看看：数据结构---二叉树---堆

四.模拟实现priority_queue

1.priority_queue的主要接口框架

template<class T, class Continer = vector<T>>
class Priority_queue
{
public:
  //插入数据
  void push(const T& val)
  {
    _con.push_back(val);
    //向上调整
    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();
  }
private:
  Continer _con;//适配容器，默认是vector
};

2.堆的向上调整算法

编辑

堆的插入需要保证插入以后还是一个堆，所以这里用到了向上调整算法。

在数组中就是，插入一个数在数组的尾上，再通过向上调整算法，调整到合适的位置。

在以堆的角度来看（小堆）为例，将新插入的值看作孩子与其父亲位置的值比较，如果比父亲位置的值还要小，那就将该值与父亲位置的值进行交换，交换后将父亲位置当作新的孩子，继续与其父亲位置的值比较，这样一直向上比较并交换，直到父亲位置的值比自己小或该位置已经没有父亲了，调整结束。

编辑

//向上调整算法
  void adjust_up(size_t child)
  {
    //1.计算父亲
    size_t parent = (child - 1) / 2;
    while (child > 0)
    {
      //如果孩子比父亲大，就交换，否则就直接推出
      if (_con[parent]< _con[child])
      {
        swap(_con[parent], _con[child]);
        //交换之后，父亲成为新的孩子，继续算新的父亲，直到没有孩子了
        child = parent;
        parent = (child - 1) / 2;
      }
      else
      {
        break;
      }
    }
  }

3.堆的向下调整算法

向下调整算法（大堆为例）:从第一个结点开始，找到其孩子结点中较大的一个与父亲位置进行交换，然后将孩子作为新的父亲，再次比较和交换，直到父亲结点比两个结点的值都大或者已经没有孩子了为止。

//向下调整
  void adjust_down(size_t parent)
  {
    //计算出左孩子
    size_t child = parent * 2 + 1;
    while (child < _con.size())
    {
      //判断是否有右孩子，右孩子是否比左孩子大
      if (child + 1 < _con.size() && _con[child]< _con[child + 1])
      {
        child++;
      }
      //较大的孩子如果比父亲大就交换，否则就直接退出循环
      if (_con[parent]< _con[child])
      {
        swap(_con[child], _con[parent]);
      }
      else
      {
        break;
      }
      //孩子成为新的父亲，继续算出新的孩子
      parent = child;
      child = parent * 2 + 1;
    }
  }

4.仿函数控制大小堆

//比较小于的仿函数，控制大堆
  template<class T>
  struct less
  {
    bool operator()(const T& val1,const T& val2)
    {
      return val1 < val2;
    }
  };
  //比较大于的仿函数，控制小堆
  template<class T>
  struct grater
  {
    bool operator()(const T& val1, const T& val2)
    {
      return val1 > val2;
    }
  };
template<class T, class Continer = vector<T>，class Compare =less<T>>//默认大堆
class Priority_queue
{
public:
    Compare com;
  //插入数据
  void push(const T& val)
  {
    _con.push_back(val);
    //向上调整
    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();
  }
private:
  Continer _con;//适配容器，默认是vector
};

五.priority_queue模拟实现整体代码和测试

Queue.hpp:

template<class T, class Continer = vector<T>,class Compare =less<T>>
  class Priority_queue
  {
  public:
    Compare com;
    void push(const T& val)
    {
      _con.push_back(val);
      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:
    //向上调整算法
    void adjust_up(size_t child)
    {
      size_t parent = (child - 1) / 2;
      while (child > 0)
      {
        if (com(_con[parent] , _con[child]))
        {
          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() && com(_con[child],_con[child + 1]))
        {
          child++;
        }
        if (com(_con[parent] , _con[child]))
        {
          swap(_con[child], _con[parent]);
        }
        else
        {
          break;
        }
        parent = child;
        child = parent * 2 + 1;
      }
    }
  private:
    Continer _con;
  };
}

main:

#include<iostream>
#include<vector>
#include<list>
using std::vector;
using std::list;
using std::cout;
using std::endl;
using std::swap;
#include"Queue.hpp"
using namespace Qikun;
int main()
{
  //小堆
  Priority_queue<int,std::vector<int>, greater<int>> small_q;
  //插入数据
  small_q.push(2);
  small_q.push(27);
  small_q.push(25);
  small_q.push(244);
  small_q.push(212);
  small_q.push(9);
  //连续取出堆顶数据打印
  std::cout << "小堆：";
  while (!small_q.empty())
  {
    cout << small_q.top()<<' ';
    small_q.pop();
  }
  cout  << endl;
  //大堆
  Priority_queue<int, vector<int>, less<int>> big_q;
  //插入数据
  big_q.push(2);
  big_q.push(27);
  big_q.push(25);
  big_q.push(244);
  big_q.push(212);
  big_q.push(9);
  //连续取出堆顶数据打印
  cout << "大堆：";
  while (!big_q.empty())
  {
    cout << big_q.top() << ' ';
    big_q.pop();
  }
  return 0;
}

编辑

C++ STL priority_queue

一.认识priority_queue

二. priority_queue的使用