因为堆是一棵完全二叉树,所以对于一个节点数为\(n\)的堆,它的高度不会超过\(log\) \(n\),所以对于插入,删除操作复杂度为\(O(log\) \(n)\),查询堆顶操作的复杂度为\(O(1)\)。

可以用来维护若干贪心题,如数据备份(用堆来实现反悔),超市(也是一种反悔)。

用对顶堆(一个大根堆一个小根堆)维护一些查询第k小/大的操作,如中位数黑匣子

具体实现为,使用两个堆,大根堆维护较小的值,小根堆维护较大的值,即小根堆的堆顶是较大的数中最小的,大根堆的堆顶是较小的数中最大的。

将大于大根堆堆顶的数(比所有大根堆中的元素都大)的数放入小根堆,小于等于大根堆堆顶的数(比所有小根堆中的元素都小)的数放入大根堆。

那么就保证了所有大根堆中的元素都小于小根堆中的元素。

\(code\):

int top()
{
    return val[1];  
}
void add(int x)
{
    int p=++siz,fa;
    val[siz]=x;
    while(p>1)
    {
        fa=p>>1;
        if(val[fa]<=val[p]) break;
        else swap(val[fa],val[p]);
        p=fa;
    }
}
void del()
{
    int p=1,son;
    val[1]=val[siz--];
    while((p<<1)<=siz)
    {
        son=p<<1;
        if(son<siz&&val[son]>val[son+1]) son++;
        if(val[p]<=val[son]) break;
        else swap(val[p],val[son]);
        p=son;
    }   
}

也可以用\(STL\)中的优先队列来实现。

priority_queue<node> q;//默认为大根堆
priority_queue<int,vector<int>,less<int> > b;//大根堆
priority_queue<int,vector<int>,greater<int> > s;//小根堆
//注意greater<int>和后面的>要隔一个空格,不然会被编译器识别成位运算符号>>
q.top()//取得堆顶元素,并不会弹出
q.pop()//弹出堆顶元素
q.push()//往堆里面插入一个元素
q.empty()//查询堆是否为空,为空则返回1否则返回0
q.size()//查询堆内元素数量
上一篇:C++ STL之priority_queue的基本用法


下一篇:C++ STL 优先队列(priority_queue)容器的简单使用