公司做网站推广百度和阿里巴巴,无忧自助建站,西安平面设计公司排行,wordpress怎么修改网站标题完全二叉树与堆 前言优先队列#xff1a;堆向下调整维护堆向上调整维护堆堆的作用 前言
本文算是补充之前的系列#xff0c;在前文中#xff0c;讲了二叉树的基本结构与应用 二叉树从入门到AC#xff08;1#xff09;构建和前中后序遍历 二叉树从入门到AC#xff08;2堆向下调整维护堆向上调整维护堆堆的作用 前言
本文算是补充之前的系列在前文中讲了二叉树的基本结构与应用 二叉树从入门到AC1构建和前中后序遍历 二叉树从入门到AC2深度与层次遍历 二叉树的特殊形态 二叉树有两种常用的特殊形态满二叉树和完全二叉树。如果一颗二叉树其内部每个结点都有左右儿子我们称之为满二叉树这很好理解如图所示
我们在满二叉树中的最后一层从右往左连续拔去至少零个结点便是完全二叉树。也就是说满二叉树是一种特殊的完全二叉树。 以上都为完全二叉树 那么如何判断一棵树是不是完全二叉树呢我们可以运用层次遍历的结构前文有代码首先将储存一颗非空树在队列中遵循 1.如果遇到一个结点左孩子为空右孩子不为空则该树一定不是完全二叉树 2.如果遇到一个结点左孩子不为空右孩子为空或者左右孩子都为空且则该节点之后的队列中的结点都为叶子节点该树才是完全二叉树 3.以上两个一直都没触发说明是满二叉树
优先队列堆
堆是一种特殊的完全二叉树每个结点储存一个值其中若所有父结点都小于其子结点称为最小堆反之则是最大堆。如图 二叉堆是一种基础数据结构C 的STL中的优先队列就是使用二叉堆。另外堆排序也是一种二叉堆算法。 堆的作用主要面向一个问题如何高效的在一组数据中任意插入删除任何值的情况下始终找到最小值/最大值。 这种数据结构也被称为优先队列。
向下调整维护堆
以上图的最小堆为例在数组中按层次遍历储存为3579811 要求不限次数的删除最小值并插入进新的值保持堆的属性最小值在堆顶 这时候我们删除堆顶的最小值3并且添加任意一个数如10到堆顶只要能维护这个堆的属性我们就可以得到新的最小值。 于是设计算法我们从堆顶开始反复执行把当前结点与左右儿子比对并与最小的那个结点交换值直到无法交换要么是左右儿子都更大要么是到叶子结点了 如图所示 于是我们维护住了一个最小堆最大堆也是同理。那么在代码层就好写多了我们可以根据数组下标发现设当前结点下标为i,我们只需要每次与2i和2i1相比并判断是否Swap就好
void Sswap(int a,int b)
{int c0;carr[b];arr[b]arr[a];arr[a]c;
}
void siftdown(int i)//向下调整用于寻找最值
{int t0,flag0;while(i*2nflag0){if(arr[i]arr[i*2])ti*2;elseti;if(t*21n){if(arr[t]arr[i*21])ti*21;}if(t!i){Sswap(t,i);//交换两结点的值it;}elseflag1;}
}在主函数中我们将数组调整为全局变量并且i始终设为0例如
int arr[6]{10,5,7,9,8,11};
int n5;
int main()
{siftdown(0);for(int i0;in;i){printf(%d ,arr[i]);}return 0;
}执行结果
向上调整维护堆
如果我们需要不断向堆中添加数值而不删除数值怎么办那么我们可以从下面的叶子结点开始添加并逐一往上比对来维护堆。
void siftup(int i)
{int flag0;if(i0)return;while(i!0flag0){if(arr[i]arr[i/2])Sswap(i,i/2);elseflag1;ii/2;}
}我们将arr[6]{3,5,7,9,8,1}; 与i5代入
这便是堆的维护操作。
堆的作用
当我们输入一个数组并求其最值时我们一般会开max或min比对每个数并保留最值这是时间复杂度最低的做法为O(N)。但是当我们删除最小值并添加进一个新值之后就相当于需要彻底进行一次重新排序复杂度也来到了O(N^2)而同样的目的由于堆的特性维护起来只需要logN的时间。 那么我们如何用完全无序的数列建立一个堆呢
void creat()
{int i0;for(in/2;i0;i--){siftdown(i);}
}即可。 在创建了堆之后我们还有著名的排序方法堆排序网上到处都有模板在这里不赘述。另外堆也是一种重要的优化思路出现在别的算法中主旨都在于用更短的时间来在插入、删除元素的情况下捕捉最值或者第n大的值也可以。
