堆实现,利用priority_queue实现可删除堆

堆基本知识:什么是堆(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大