学习数据结构（11）二叉树（堆）下

1.堆的概念

如果有⼀个集合 K = {k0，k1，k2，...，k(n-1)} ，把它的所有元素按完全二叉树的形式存储在一个一维数组中，并满足：K(i)<=2*i+1且K(i)<=2*i+2（K(i)>=2*i+1且K(i)>=2*i+2），i=0,1,2... ，则称为小堆(或大堆)，将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆

例：有一组数据：10，65，70，30，15，25

                                

2.堆的实现

（1）初始化堆

（2）堆的销毁

（3）交换

（4）堆的插入

 （5）向上调整

为了构建小堆或大堆，在插入数据时，可以将插入的数据看作孩子，在满足双亲的下标>=0(孩子的下标大于0)将孩子与双亲作对比，向上调整数据

图例：

向上调整算法的时间复杂度：（为了简化使用满二叉树来证明）

则每层节点需要移动的次数为:每层结点的个数*向上移动的次数，节点总共需要移动的次数为：所有层节点需要移动的次数之和

T(h)=2^1*1+2^2*2+2^3*3+...+2^(h-2)*(h-2)+2^(h-1)*(h-1)                       ①

2*T(h)=2^2*1+2^3*2+2^4*3+...+2^(h-1)*(h-2)+2^(h)*(h-1)                       ②

①-②：-T(h)=2^1+2^2+2^3+...+2^(h-2)+2^(h-1)-2^h*(h-1)                                                                                    =2^h-2-2^h*(h-1)                                                                                                                                =2^h(2-h)-2

T(h)=2^h(h-2)+2，根据二叉树的性质：n=2^h-1,h=log2(n+1)

得F(n)=(n+1)(log2(n+1)-2)+2,故向上调整算法的时间复杂度为：O(n*log2(n))

（6）打印堆

（7）判空

 （8）堆的删除

删除堆顶数据就是将数组开头的元素和数组末尾的元素交换，将堆中size的值减一，此时堆中的结构可能被改变，不再是大堆(小堆)，需要将堆顶元素向下调整

（9）向下调整

以此时的堆顶元素为双亲，在满足孩子的下标小于堆元素个数的情况下，与两个孩子作对比（如果没有右孩子，则只和左孩子做对比），不断向下调整数据

图例：

向下调整算法的时间复杂度：（为了简化使用满二叉树来证明）

则每层节点需要移动的次数为:每层结点的个数*向下移动的次数，节点总共需要移动的次数为：所有层节点需要移动的次数之和

T(h)=2^0*(h-1)+2^1*(h-2)+2^2*(h-3)+...+2^(h-3)*2+2^(h-2)*1                       ①

2*T(h)=2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+...+2^(h-2)*2+2^(h-1)*1                    ②

②-①：T(h)=2^1+2^2+2^3+...+2^(h-2)+2^(h-1)+1-h                                                                                             =2^h-1-h

根据二叉树的性质：n=2^h-1,h=log2(n+1) 

T(n)=n-log2(n+1)，故向下调整算法的时间复杂度为O(n)                        

（10）取堆顶元素

3.堆排序

（1）在数据结构堆中实现排序

创建数据结构堆，将数组中的元素一一插入堆中，在堆不为空的情况下，循环取堆顶放入数组中，再删除堆顶，每次取出的堆顶都是堆中的最大值或最小值，由此实现升序或降序排列

（2）利用堆的思想在数组中实现排序

通过向上调整或向下调整将数组排列成堆的结构（若要排升序，则建大堆，排降序，则建小堆），将数组开头的元素和末尾的元素交换，将此时数组开头的元素看作双亲，向下调整

堆排序算法的时间复杂度为：O(nlog2(n))，效率高于冒泡排序