堆基本知识：什么是堆（Heap）_堆是什么-CSDN博客

优先队列priority_queue

priority_queue带有权值概念，其内的元素并非依照被推入的次序排列，而是自动依照元素的权值排列（通常权值以实值表示）。权值最高者，排在最前面。

缺省情况下，priority_queue利用一个max-heap完成，后者是以一个vector表现的完全二叉树。max-heap可以满足priority-queue所需要的“依权值高低自动递减排序”的特性。

由于priority_queue完全以底部容器为根据，再加上heap处理规则，实现非常简单。缺省情况下是以vector为底部容器。

priority_queue以底部容器完成其所有工作，具有这种“修改某物接口，形成另一种风貌”的性质者，称为adapter(配接器)。因此，STL priority_queue往往不被归类为contcainer容器，而被归类为container adapter。

template<class T, class Sequence = vector<T>, class Compare = less<typename Sequence::value_type>>
class priority_queue{
public:
	typedef typename Sequence::value_type value_type;
    typedef typename Sequence::size_type size_type;
    typedef typename Sequence::reference reference;
    typedef typename Sequence::const_reference const_reference;
    
protected;
    Sequence c;		//底部容器
    Compare comp;	//元素大小比较标准

public:
    priority_queue() : c() {}
    explicit priority_queue(const Compare& x) : c(), comp(x) {}
    
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last, const Compare& x) :
    	c(first, last), comp(x) { make_heap(c.begin(), c.end(), comp); }
    template <class InputIterator>
    priority_queue(InputIterator first, InputIterator last) :
    	c(first, last) { make_heap(c.begin(), c.end(), comp); }
    
    bool empty() const { return c.empty(); }
    size_type size() const { return c.size(); }
    const_reference top() const { return c.front(); }
    void push(const value_type& x){
        __STL_TRY{
            c.push_back(x);
            push_heap(c.begin(), c.end(), comp);
        }
        __STL_UNWIND(c.clear());
    }
    void pop(){
        __STL_TRY{
            pop_heap(c.begin(), c.end(), comp);
            c.pop_back();
        }
        __STL_UNWIND(c.clear());
    }
};

 priority_queue的所有元素，进出都有一定的规则，只有queue顶端的元素（权值最高者），才有机会被外界取用，priority_queue不提供遍历功能，也不提供迭代器。

堆实现

优先队列(Priority Queue)

理论上二叉堆可以支持O(log N)删除任意元素，只需要

● 定位该元素在堆中的结点p (可以通过在数值与索引之间建立映射得到)
● 与堆尾交换，删除堆尾
● 从p向上、向下各进行一次调整
不过优先队列并没有提供这个方法，在各语言内置的库中，需要支持删除任意元素时，一般使用有序集合等基于平衡二叉搜索树的实现。

template<typename T>
class priority_queue_plus : public std::priority_queue<T, std::vector<T>>
{
public:
    bool remove(const T& value) {
        auto it = std::find(this->c.begin(), this->c.end(), value);
        if (it != this->c.end()) {
            this->c.erase(it);
            std::make_heap(this->c.begin(), this->c.end(), this->comp);
            return true;
        } else {
           return false;
        } 
    }
};

如果是存放结构体，且要自定义比较函数，可以用仿函数，就是用写一个结构体，然后重载()运算符。

priority_queue<int> pq;//默认为大根（顶）堆

priority_queue<int, vector<int>, greater<int> > pq2;//修改为小根（顶）堆

struct Node
{
    int a, b;
};//声明Node结构体

struct cmp
{
    bool operator () (const Node &u, const Node &v)const
    {
        return u.a < v.a;
    }
};

priority_queue<Node, vector<Node>, cmp> pq_Node;

 另一种C++实现

C++ 堆、大顶堆、小顶堆、堆排序-CSDN博客

堆算法题

双堆实现滑动窗口第K大