详解“为何建堆的时间复杂度O(N)?“+“排升序为什么不能建小堆？”

目录

一.向上调整法建堆的时间复杂度O(N)计算

二.向下调整法建堆的时间复杂度O(N)计算

结论：

        向上调整法建堆 的 时间复杂度是 O(N*logN)，

        向下调整法建堆 的 时间复杂度是 O(N)， 因此 向下调整法建堆 更优！！！

三.堆排序如果要排升序为什么要建小堆？

---

我们先来回顾一下堆排序：(需要有堆相关内容基础，详情可见我的上一篇文章(33条消息) “堆的增删查改“以及“堆排序“详解_beyond.myself的博客-CSDN博客)
对于一个数组int a[ ]，我们对他进行堆排序的操作有两类操作：

①新创建一个堆 hp ，把数组a中的数据通过"堆添加函数" HeapPush 一个一个放到堆的数组中，因为 堆添加函数 内部自带 向上调整算法AdjustUp ，因此会自动把插入的数据进行排序成小根堆，△ 再利用 HeapTop找堆顶数据函数把堆顶数据(最小的数据)赋给原数组a， 再通过 HeapPop堆顶删除函数 删除堆顶数据，因为HeapPop内部自带向下调整算法，所以删完依然会调整为小根堆，再从△处操作重复拿次小数据，删数据，直到堆 hp 空停止，此时原数组a内的数据就是已经排好升序。（因为这个思路的前提是需要堆的增删查改，因此我们说写堆排序时强烈不推荐这种写法）

②建好大堆后交换堆顶队尾数据，把堆尾数据排除在外，再整体向下调整，通俗来说就是建大堆，按从大到小依次把数据放在最后一位，倒数第二位，倒数第三位……，并且每次用一个 end=size-1 做下标计数器，放一次就 -- 一次，就可以实现堆排序。这里有两种建大堆的方式：向上调整法建大堆，向下调整法建大堆。

那在堆排序中，我们到底用哪一种建堆方式更优呢？由此我们来讨论一下这两个建堆的时间复杂度大小……

一.向上调整法建堆的时间复杂度O(N)计算

(建大堆，建小堆时间复杂度是一样的，所以我们不必纠结这个，只看运行次数即可)

先给出向上调整法的函数：

void AdjustUp(HPDataType* a, size_t child)
{
	size_t parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[child] > a[parent])		//大堆
		{
			swap(&a[child], &a[parent]);
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}

 向上调整法建堆的代码：

//从数组第2个数直到最后一个数重复进行向上调整算法
for(int i=1;i<n;i++)
{
    AdjustUp(a,i);
}

在AdjustUp 函数中有一个循环，假如里面有2个需要运算的式子并且循环了n次，一共2n次，时间复杂度会省略系数，所以还是O(N)，所以我们只需要看这个循环循环多少次即可，就看swap交换函数执行次数就能知道循环多少次，即看交换了多少次就能求出时间复杂度。

假设一个深度是h层的满二叉树(因为是考虑最坏情况，所以我们就算满二叉树时间复杂度即可)，它的第一层是1个节点： 2^0, 若执行向上调整法，就他自己一个没必要执行：比较0次

它的第二层是2个节点：2^1,若执行向上调整法，最多往上比较一层就够了：比较1次

它的第三层是4个节点： 2^2,若执行向上调整法，最多往上比较二层就够了：比较2次

……

它的第h层有这么多节点：2^(h-1),若执行向上调整法，最多往上比较h-1层就够了：比较h-1次

把他们相乘再相加就是总的循环次数。总次数设为T(h)

①T(h)= 2^0*0 + 2^1*1 +  2^2*2 + …… + 2^(h-1)*(h-1)  等比数列×等差数列求和，用错位相减法：

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

(错位相减法：等式两边同时乘q，再相减)     

②-①：

T(h) = -2^0*0 - 2^1 -  2^2 - …… -2^(h-1) + 2^h*(h-1) 

       = -( 2^1 + 2^2 + …… +2^(h-1)) ) + 2^h*(h-1)         等比数列求和公式：a1*(1-q^n)/(1-q)

       = -2*(1-2^(h-1))/(1-2) + 2^h*(h-1)

       = 2 - 2^h + 2^h*(h-1)

       = 2 + 2^h*(h-2)

由：总结点数公式 N = 2^h - 1 , N + 1 = 2^h , h = log2(N+1) 带入上式：

T(h) = 2 + 2^log2(N+1) * ( log2(N+1) - 2 ) = 2 + (N+1) * ( log2(N+1) - 2 )

时间复杂度的计算省去所有常数和系数，凡是log以几为底N的对数统统写成logN，

因此 2 + (N+1) * ( log2(N+1) - 2 ) 就是N*logN

求得 向上调整法建堆 的 时间复杂度就是 O(N*logN)

二.向下调整法建堆的时间复杂度O(N)计算

先给出向上调整法的函数：

void AdjustDown_better(HPDataType* a, size_t size, int parent)
{
	size_t child = parent * 2 + 1;				
 
	while (child < size)
	{
		if (child + 1 < size && a[child + 1] > a[child]) 
		{
			child++;
		}
		if (a[child] > a[parent])		//大堆
		{
			swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

 向上调整法建堆的代码：

//从最后一个叶子的父亲开始，不断--，直到第一个节点(包括第一个节点)，重复进行向下调整算法
//n-1是最后一个叶子节点的数组下标
//(n-1-1)/2是最后一个叶子节点的父亲的数组下标 
//利用公式：child=2*parent+1; parent=(child-1)/2 所得
for(int i=(n-1-1)/2;i>=0;i--)
{
    AdjustDown(a,n,i);
}

计算AdjustDown 函数内的循环的循环次数就是时间复杂度：

假设一个深度是h层的满二叉树(因为是考虑最坏情况，所以我们就算满二叉树时间复杂度即可)，第1层有2^0个节点:若执行向下调整法，下面有多少层就最多执行多少次，下面有h-1层:执行h-1次

第2层有2^1个节点:最多向下调整h-2层:执行h-2次

第3层有2^2个节点:最多向下调整h-3层:执行h-3次

……

第h-1层有2^ (h-2)个节点:最多向下调整h-1层:执行1次

第h层有2^ (h-1)个节点:最多向下调整h-1层:执行0次

把他们相乘再相加就是总的循环次数。总次数设为T(h)

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

等比数列×等差数列求和，继续用错位相减法：

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

(错位相减法：等式两边同时乘q，再相减)     

②-①：

T(h) = -2^0*(h-1) + 2^1 +  2^2 + …… + 2^(h-1) 

       =  -2^0*(h-1) + 2*(1-2^(h-1))/(1-2)      等比数列求和公式：a1*(1-q^n)/(1-q)

       =  1-h + 2^h -2

       =  -1-h + 2^h

由：总结点数公式 N = 2^h - 1 , N + 1 = 2^h , h = log2(N+1) 带入上式：

T(h) = -1-log2(N+1)  + 2^log2(N+1) = -1-log2(N+1) + N+1 = -log2(N+1) + N

时间复杂度的计算省去所有常数和系数和对表达式影响小的项，因为logN相比N对表达式影响很小，所以省略logN，因此 -log2(N+1) + N 就是N

求得 向下调整法建堆 的 时间复杂度就是 O(N)

结论：

        向上调整法建堆 的 时间复杂度是 O(N*logN)，

        向下调整法建堆 的 时间复杂度是 O(N)， 因此 向下调整法建堆 更优！！！

三.堆排序如果要排升序为什么要建小堆？

堆排序一共二个步骤：建堆，排序

此问题就是讨论堆排序的第二个步骤：排序

假设给出一个乱序的堆：0 1 2 6 5 4 7 8

我们知道，排升序如果建大堆后，只需将堆顶和队尾交换，不把最后一个数当做堆的数据，就是移除第一个数据(具体操作就是end=size-1；end--)，然后再把前面的整个堆进行向下调整形成新的大堆，然后再交换——移除——调整，重复操作：相当于就是从堆顶不断拿最大的数据放到队尾，最后就能成为升序。

那排升序如果建小堆呢？最小的数已经在第1个位置了，我们只能不把第一个数当做堆的数据，对剩下的数据进行调整成新的小堆，但是移除第一个数据后剩下的数关系全部乱了，无法达到向下调整法的条件(左右子树都是小堆)，所以无法使用一次向下调整将其排成小堆，只能重新建堆，然后才能选出次小的，不断建堆选数。但是建堆时间复杂度是O(N)，每选一个次小的数都要O(N)，总的时间复杂度就是O(N²)，还不如直接遍历选数。可以是可以，但是效率不行，还复杂!所以就非常不推荐排升序建小堆了！