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

堆与优先队列

2024-10-25 05:41:02   212人阅读

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

　　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

 

堆与优先队列


联系
我们