跳转至

priority_queue(堆排序)

priority_queue优先队列

  • 从后面入队，从前面出队
  • 入队时，会让优先级高的排在队伍前面
  • 下标为0的地方是top栈顶；下标为size-1的地方是栈底bottom
  • 内部实现是堆排序
  • 不会去重

#include<queue>

template <
    typename T,  //元素类型
    typename Container=std::vector<T>, 
        //优先队列的底层容器，必须是数组(如vector、deque)，不能是list 
    typename Compare=std::less<T>
        //默认是less
> 
class priority_queue;

大顶堆、小顶堆如何区分

背景

  • std::sort默认是使用<号进行排序，而且是升序（因为设计者们认为，升序是常见的排序方式）。如果传入>，则是降序
  • 对于priority_queue，新元素是从右边插队，因此顺序是从右到左

如何区分

//大顶堆（默认）
priority_queue <int,vector<int>,less<int> >q;
//less => （从右到左）升序 => 队头是大值（左边是队头） => 大顶堆

// 小顶堆
priority_queue <int,vector<int>,greater<int> > q;
//greater => （从右到左）降序 => 队头是小值（左边是队头） => 小顶堆