数据结构-堆排序及其复杂度计算_堆排序的复杂度

目录

1.堆排序

1.1 向上调整建堆

1.2 向下调整建堆

2. 两种建堆方式的时间复杂度比较

2.1 向下调整建堆的时间复杂度

2.2 向上调整建堆的时间复杂度

Topk问题

---

上节内容，我们讲了堆的实现，同时还包含了向上调整法和向下调整法，最后我们用堆实现了对数据的排序：

int main()
{
	HP hp;
	HeapInit(&hp);
	int arr[] = { 65,100,70,32,50,60 };
	int i = 0;
	for (i = 0; i < sizeof(arr) / sizeof(int); i++)
	{
		HeapPush(&hp, arr[i]);
	}
	while (!HeapEmpty(&hp))
	{
		HeapDatatype top = HeapTop(&hp);
		printf("%d ", top);
		HeapPop(&hp);
	}
	return 0;
}

那以上代码能实现对数据的排序吗?

答案是可以的，但是以上方式有两个弊端：

1. 要先写一个堆，太麻烦

2. 空间复杂度+拷贝数据。

1.堆排序

上节内容中，用堆对数据进行排序，是将数据一个一个插入堆，然后再调整排序的，那我们能不能直接把数据就建成一个堆？

当然可以，建堆有两种方式：向上调整建堆、向下调整建堆。

1.1 向上调整建堆

我们先来讲向上调整建堆：

向上调整建堆其实还是插入堆的逻辑，要求前面的数据必须是一个堆，下标从1开始是因为一个数据本身就可以被看做一个堆，然后向上调整。 

下图就是我们对一个数组数据进行向上调整建堆后的结果，可以看出来，此时我们建的是一个小堆： 

现在问题来了，我们要把数据排为升序，建大堆还是建小堆好？

先说结论：升序 -- 建大堆    降序 -- 建小堆。 

假设我们要得到升序，此时又建的是小堆，那我们就把选出的最小的数据放在下标为0的位置，要想继续选出次小的数据放在下标为1的位置，就要把剩下的数据看做堆，这样堆的关系就全乱了，只能重新建堆，代价太大。

而如果我们建大堆，向下调整选出最大的数据，首尾交换，把最大的数据放在最后一个下标的位置，然后隔离最后一个数据，把其他数据看做一个堆，再向下调整选出次大的，首尾交换......直到所有的数据被排好序，此时得到的就是数据升序。

代码如下：

#define  _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
 
typedef int HeapDatatype;
 
swap(HeapDatatype* p1, HeapDatatype* p2)
{
	HeapDatatype tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整法
void AdjustUp(HeapDatatype* a, int child)
{
	int parent = (child - 1) / 2;
	while (child > 0)
	{
		if (a[parent] < a[child])
		{
			HeapDatatype p = a[parent];
			a[parent] = a[child];
			a[child] = p;
			child = parent;
			parent = (child - 1) / 2;
		}
		else
		{
			break;
		}
	}
}
//向下调整法
void AdjustDown(HeapDatatype* a, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		if (child + 1 < n && a[child] < a[child + 1])
		{
			child++;
		}