简介:

一:定义以及部分性质

1:堆中某个节点的值总是不大于或不小于其父节点的值;

2:堆总是一棵完全二叉树。

3:最后一个非叶结点是第n/2个结点。这里建堆的时候会用到,复杂度可以降到O(n);

二:关于建堆

如果一个点为u,那么它的左儿子为2u,右儿子为2u+1

对于小根堆来讲,每个以u为根节点的树,它的左右儿子的值一定大于父节点。

所以对堆进行建立的时候,如果当前点与它的左右儿子并不满足这一性质,就需要进行交换。

对于建堆的过程:

由(一)第三条,我们建堆的时候,只需要从n/2开始,到1即可。因为已知最后一个非叶结点是n/2,那么>n/2的结点,都是叶子结点,它本身所构成的子树只有它本身。一定符合小根堆性质,所以是没必要看的。我们从第n/2结点开始,每次让它向下比较一次,变为局部的合法(比如第一次只有三个点,满足父节点都小于左右儿子结点)。然后它的向上的父节点再向下比较,那么每次比较,都会得到一个局部合法的子树(本次进行的父节点往下的子树)。所有的n/2~1都这么操作,一定可以把整个完全二叉树变成合法的小根堆。

有:

for(int i=n/2;i>=1;i--)
{
    down(i);
}

对于向下比较的过程,我们定为down(u)函数。由小根堆的性质,u为父节点,那么它的左右儿子h[2u]和h[2u+1]都要大于它,否则就要进行交换:

void down(int u)
{

//t表示三个点中的最小值 
int t=u;
//判断是否有左儿子
if(u*2<=siz&&h[2*u]<h[t]) 
{
    t=2*u;
}
//是否有右儿子
if(2*u+1<=siz&&h[2*u+1]<h[t])
{
    t=2*u+1;
}
if(u!=t)
{

     //需要交换,则交换,继续down往下判断

    swap(h[u],h[t]);
    down(t);
}

}
只要down()就可以把堆给建好了。

关于up操作:

比down更简单,只需要与它的父节点u/2进行比较即可,非法即交换。

void up(int u)
{

while(u/2>=1&&h[u/2]>h[u])
{
    swap(u,u/2);
    u=u/2;
}

}
三:堆的操作

定siz为树大小

1:插入一个数:

直接在末尾加一个,所以++size处插入新数,然后进行更新树。由于此时它处于树的最底部,所以直接up(size)即可。

2:求集合中最小值:

h[1]

3:删除最小值:

把树尾覆盖上去,siz--,由于此时它处于树的顶部,所以直接down(1)即可。

4:删除任意一个元素:

删除K号结点。与3类似,直接把树尾覆盖上去,siz--,但是需要up(k)或down(k)一遍,为了简便,把up和down都写上,只会执行其中一个。

5:修改任意一个元素

直接修改h[k]=x,up(k),down(k)

四:堆排序

堆的其中一个作用,堆排序:时间复杂度O(NlogN)

输入一个长度为N的整数数列,从小到大输出前M小的数

#include<cstdio>
#include<cstring>
#include<vector>
#include<set>
#include<algorithm>
#include<iostream>
#include<vector>
using namespace std;
typedef long long ll;
const int maxn=1e5+10,maxn2=31*maxn;
int n,m;
int h[maxn],siz;//1~n
void down(int u)
{
    //t表示三个点中的最小值 
    int t=u;
    //判断是否有左儿子
    if(u*2<=siz&&h[2*u]<h[t]) 
    {
        t=2*u;
    }
    if(2*u+1<=siz&&h[2*u+1]<h[t])
    {
        t=2*u+1;
    }
    if(u!=t)
    {
        swap(h[u],h[t]);
        down(t);
    }
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>h[i];
    }
    siz=n;
    for(int i=n/2;i>=1;i--)
    {
        down(i);
    }
    while(m--)
    {
        cout<<h[1]<<" ";
        h[1]=h[siz]; //更新最小值
        siz--;
        down(1);
    }
    return 0;
}
目录
相关文章
|
9月前
|
存储 算法 索引
堆的实现(C版)
堆的实现(C版)
30 0
|
2月前
|
存储 缓存 JavaScript
|
11月前
|
算法
堆的实现以及应用
我们说堆在物理上是一个数组,逻辑上它是一个完全二叉树,我们可以通过它的下标来计算父亲和孩子之间的关系。
|
存储 缓存 Java
08-堆(一)
08-堆(一)
67 0
|
存储 缓存 算法
08-堆(二)
08-堆(二)
119 0
|
存储 缓存 Oracle
08-堆(三)
08-堆(三)
67 0
|
搜索推荐
堆的应用
堆的应用
123 0
堆的应用