【第十五课】数据结构：堆 (“堆”的介绍+主要操作 / acwing-838堆排序 / c++代码 )

//调整以x为根的子树，以满足小根堆的性质(x是经过某种操作得到的值，在操作之前整棵树是满足堆的性质的)
void down(int x)
{
    int t=x;//t表示三个数中的最小值
//比较的前提都是孩子存在
    if(x*2<=size && he[x*2]<he[t])t=x*2;

    if(x*2+1<=size && he[x*2+1]<he[t])t=x*2+1;
    if(x!=t)//所以这里如果不需要交换位置，那说明更改的这个值并没有破坏原有的性质
    {
        swap(he[x],he[t]);
        down(t);//需要交换 说明我们又更改了一个位置的值，所以要继续判断这次更改的是否符合性质
    }
}

down操作的前提就是 本身这个树的每个节点都是符合性质的，只是某一个值发生了改变，

我们针对这个发生改变的值，不管它是插入还是修改还是更改而导致的值的变化，我们最主要的就是关注改值之后，以其为根节点的子树。

将该值与它的原本的左右两个孩子的值的比较，如果不需要交换位置，说明这次的更改的值并没有引起堆的性质的变化

up

如上图这种完全二叉树，按照数组存储方式，观察其下标表示，我们发现孩子节点是其父节点下标的二倍。

由于小根堆的性质，根节点小于左右孩子，所以我们检查的时候只看该节点与根节点的大小关系就好了，因为另一个孩子一定是大于根节点且符合性质的。

void up(int x)
{
    while(x/2 && he[x/2]>he[x])//当该元素存在父节点且满足大小关系
    {
        swap(he[x/2],he[x]);
        x /= 2;//更新父节点
    }
}

有了上面down的详细解释这个应该很容易理解了。?

数据结构：堆的主要操作

1.插入一个元素，并仍保持堆的性质。

2.删除最小/大值。

3.堆化：将一个无序数组转换为堆，或者修复一个破坏了堆性质的堆。

这里先详细说一下堆化

for(int i=n/2;i;i--)down(i);

我们通常从倒数第二层(n/2是最后一个元素的父节点)开始进行逐个元素下沉，最终达到将数组堆化的结果。?这是因为底层节点是叶子节点，它们自身已经满足堆的性质，不需要进行下沉操作。

关于手写堆的一些主要操作就是上面这些。

下面我逐个来解释。

1.插入一个数。由于我们堆结构是用数组实现存储的完全二叉树，因此对于数组来说，在末尾添加一个元素是很容易的，所以我们先把这个要插入的元素放到堆的末尾，在进行up操作，使其符合堆的性质。

2.求最小值，我们小根堆的根节点就是其最小值。

3.删除最小值。由于我们总是要删除一个元素的，在数组存储结构中，删除最后一个元素是很简单的，直接使我们使用到的下标--就行，但是我们要删的是第一个元素呀，怎么办呢？我们把最后一个元素的值标记覆盖到第一个元素的位置，再删除掉最后一个元素，再把刚刚放到第一位的元素进行down操作，使其符合堆的性质。

4.删除任意一个元素。在3思路的基础上，由于我们不清楚最后一个元素相较于原来这个位置上删除掉的元素是大还是小，如果是大于原来的元素，那就会执行down，如果小于，就会向上执行up，因此，这两个只会执行其中一个，为了简化代码，我们直接不判断，把两个都放上去。

5.修改任意一个元素，解释同4

acwing-838堆排序

经过上面的介绍其实这道题的核心都已经解了，直接看代码把。

代码如下

#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e5+10;
int n,m;
int he[N],size;

//调整以 x 为根的子树，以满足小根堆的性质
void down(int x)
{
    int t=x;//t表示三个数中的最小值
    if(x*2<=size && he[x*2]<he[t])t=x*2;
    if(x*2+1<=size && he[x*2+1]<he[t])t=x*2+1;
    if(x!=t)
    {
        swap(he[x],he[t]);
        down(t);
    }
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&he[i]);
    }

    size=n;//size标记数组最后一个元素

    for(int i=n/2;i;i--)down(i);//将数组堆化
    
    while(m--)//每次输出一个最小值
    {
        printf("%d ",he[1]);
        he[1]=he[size];//删除最小值
        size--;
        down(1);
    }
    return 0;
}

时间复杂度分析

在这段代码中：

①输入数据的for循环O(n)?

②建堆的for循环，先看down函数，down是逐层比较，其时间复杂度取决于树的高度，所以最坏情况下就是该二叉树为满二叉树时的树高，即log(n)。那么真整个建堆过程时间复杂度应为O(n*log(n))?

--关于这里的时间复杂度其实还有一种思考方式，等之后回来补写一下。

③输出最小值的while循环，也是取决于down函数执行次数，即O(m*log(n))?

哎，就差一个模拟堆(烦躁)，是有点强迫症在的😢明天在写啦。。

有问题欢迎指出！一起加油！！

文章来源:https://blog.csdn.net/Swillow_/article/details/135768922
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系我的编程经验分享网邮箱：chenni525@qq.com进行投诉反馈，一经查实，立即删除！