上次通过数组实现堆排序的时间复杂度为O(NlogN),空间复杂度为O(N)。

优化后时间复杂度O(NlogN),空间复杂度O(1).

考虑优化方案：

1.向下调整建堆。

2.向上调整建堆。

建堆只是为了找到堆中最大或者最小的元素。

1.向上调整建堆

使用向上调整，插入数据的思想建堆。

优化方案本质上就是不开辟新的空间在原数组上进行处理，使其空间复杂度变为O（1）。

void HeapSort2(int* a,int n)
{
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
	for(int i= 0;i<n;i++)
		printf("%d ", a[i]);
	printf("\n");
}

现在对其时间复杂度进行计算，为方便计算，采用满二叉树来计算。

以下考虑的是最坏的境况：

第二层： 2^1 个结点 ，向上调整1层；

第三层： 2^2 个结点 ，向上移动2层；

……

第h层：2^(h-1)个结点，向上移动h-1层。

则需要移动的结点的次数：

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

根据数列错位相减法求和公式可知

T(n) = (N+1) * ( log(N+1) - 2 )+2 当n->无穷大  T(n) = NlogN

向上建堆的时间复杂度为O(N*logN).

2.向下调整建堆

前提要求：对必须是大堆或者小堆。

所以要先对数组进行调整。

从倒数第一个非叶子结点开始（最后一个结点的父亲结点）。

因为叶子结点可以单独看作大堆或者小堆。

画图：

调整次数：4次

代码：

void HeapSort3(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
 
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

空间复杂度：O（1），时间复杂度O（N）

现证明时间复杂度：

第一层：2^0个结点，需要向下移动h-1层。

第二层：2^1个结点，需要向下移动h-2层。

第三层：2^2个结点，需要向下调整h-3层。

……

第h-1层，2^(h-2)个结点，需要向下移动1层。

所以移动的总次数：

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

根据错位相减法可得出：

T(n) = 2^h - 1 - h

又 n = 2^h - 1

T(n) = n - log(n+1) 

当n无穷大时，近似认为T(n) = n

证明完毕。

既然已经有向上建堆和向下建堆两种方法，那么哪种情况更是配建小队，哪种更适合见大堆？？

升序 -- 建大堆

理由：若是升序建小堆最小的数已经在第一个位置了，剩下的关系全都乱了，需要重新建堆，建堆要O(N),再选出次小的，不断建堆选数，如此以时间复杂度O(N)的情况还不如直接遍历轻松。

总之，升序建小堆，效率低，还复杂。

降序--建小堆

那如何建大堆完成排序呢？

建大堆本质上就是尽可能维持堆的稳定。

找到最大的数后，将根位置的数与最后一个数相交换，在n-1组数据中进行向下调整，找到次小的数，将根与第n-1位置的数交换，以此实现升序。

相关代码：

void HeapSort4(int* a, int n)
{
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		//建大堆
		AdjustDown(a, n, i);
	}
	//找到最后一个数的下标
	int end = n - 1;
	while (end > 0)
	{
		//交换根和最后一个位置的值
		Swap(&a[0], &a[end]);
		AdjustDown(a, end, 0);
		end--;
		
	}
	for (int i = 0; i < n; i++)
		printf("%d ", a[i]);
	printf("\n");
}

Top - k 问题

求数据结合中前k个最大元素或者最小的元素，一般情况下数据量都比较大。

Top-k中最简单的方法就是排序，如果数据量非常大，排序就会出现问题（数据不能一次性加载到内存中），但是堆排序可以解决。

1.用数组中前看个元素来建堆。

求最大建小堆，求最小则建大堆。

与升序建大堆，降序建小堆原理相似。

2.用剩余的n-k个元素与对顶的元素作比较，来替换对顶的元素。

记得向下调整。

void TopK(int* a,int n,int k)
{
	//建小堆
	int* topk = (int*)malloc(sizeof(int) * k);
	assert(topk);
	for (int i = 0; i < k; i++)
	{
		topk[i] = a[i];
	}
	//向下调整建堆
	for (int i = (k - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDown(topk, k, i);
	}
	for (int j = k; j < n; j++)
	{
		if (topk[0] < a[j])
		{
			topk[0] = a[j];
			AdjustDown(topk, k, 0);
		}
	}
	for (int i = 0; i < k; i++)
	{
		printf("%d ", topk[i]);
	}
	printf("\n");
	free(topk);
}
int main()
{    
	int n = 10000;
	int* a = (int*)malloc(sizeof(int) * n);
	assert(a);
	srand(time(0));
	for (int i = 0; i < n; i++)
	{
		a[i] = rand() % 10000;
	}
	a[0] = 100001;
	a[101] = 100002;
	a[159] = 123456;
	a[7459] = 100003;
	a[7412] = 100009;
	a[7826] = 111111;
	a[7712] = 222222;
	a[9635] = 999999;
	TopK(a,n,8);
	return 0;
}

时间复杂度 O( K+ K*log(N-K) )

空间复杂度：O(K)

当K<<N时，效率也蛮高的。

有不对的地方还请大佬指出。