首页 > 代码库 > 堆与优先队列

堆与优先队列

当我们需要高效的完成以下操作时:

  1.插入一个元素

  2.取得最小(最大)的数值,并且删除

能够完成这种操作的数据结构叫做优先队列

而能够使用二叉树,完成这种操作的数据结构叫做堆(二叉堆)

 

堆与优先队列的时间复杂度:

若共有n个元素,则可在O(logn)的时间内完成上述两种操作

 

堆的结构如下图:

技术分享

堆最重要的性质就是儿子的值一定不小于父亲的值,且堆从上到下,从左到右紧密排列。

堆的操作:

当我们希望向堆中插入元素时,堆的内部会进行如下操作(以插入元素3为例):

技术分享(1.在堆的末尾插入该值)

技术分享(2.不断向上提升该元素,直到满足堆的性质为止)

 

当我们需要删除堆中的最小值时,堆的内部则进行如下操作

技术分享(1.将堆的最后一个节点复制到根节点位置,而后删除最后一个节点)

技术分享(2.不断向下交换,直到满足堆的性质为止)

 

 

堆的代码实现:

技术分享
int heap[MAXSIZE],hsize=0;

void Push(int x) //向堆中添加元素
{
    int i = hsize++; //堆的大小增加
    while(i > 0)
    {
        int father_id = (i - 1)/2; //父亲节点的编号
        
        if(heap[i] > heap[father_id]) //判断是否满足堆的性质
            break;
        
        heap[i] = heap[father_id]; //将父亲节点下放,将新增元素上移
        i = father_id;
    }
    heap[i] = x;
}

void Pop() //弹出堆中的最小值
{
    int root = heap[0]; //记录最小值
    
    int x = heap[hsize--]; //堆的大小减少
    
    int i = 0;
    
    while(i * 2 + 1 < hsize)
    {
        int lson = i * 2 + 1; //左儿子节点
        int rsong = lson + 1; //右儿子节点
        
        if(lson > x && rson > x) //判断是否满足堆的性质
            break;
            
        if(heap[lson] < heap[rson]) //选择与儿子交换
        {
            heap[i] = heap[lson];
            i = lson;
        }
        else if(ron < hsize)
        {
            heap[i] = heap[rson];
            i = rson;
        }
    }
    
    heap[i] = x;
    
    return root;
}
View Code

 

STL中的优先队列:

在C++中,STL里的priority_queue可以完成优先队列的实现,代码如下

 

技术分享
#include<queue>
#include<cstdio>
using namespace std;

int date[5];

int main()
{
    priority_queue<int> Q; //默认为最大值优先
    priority_queue<int,vector<int>,greater<int> > Q1; //最小值优先
    priority_queue<int,vector<int>,less<int> > Q2; //最大值优先

    for(int i=1;i<=3;i++)
    {
        scanf("%d",&date[i]);
        Q.push(date[i]); //插入元素
    }


    while(!Q.empty())
    {
        int x = Q.top(); //读取队头元素
        Q.pop(); //弹出元素
        printf("%d\n",x);
    }

    return 0;
}
View Code

 

堆与优先队列