排序算法：堆排序网站首页 其他

//    堆

#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>

//创建堆
//顺序表
typedef int HPDataType;

typedef struct Heap
{
	HPDataType* a;
	int size;  //有效元素个数
	int capacity;  //容量
}Heap;

//初始化
void HeapInit(Heap* php);

//销毁
void HeapDestroy(Heap* php);

//插入
void HeapPush(Heap* php, HPDataType x);

//删除
void HeapPop(Heap* php);

//判空
bool HeapEmpty(Heap* php);

//获取堆顶元素
HPDataType HeapTop(Heap* php);

//初始化
void HeapInit(Heap* php)
{
	php->a = NULL;
	php->size = 0;
	php->capacity = 0;
}

//销毁
void HeapDestroy(Heap* php)
{
	free(php->a);
	php->a = NULL;
	php->size = php->capacity = 0;
}

//交换函数
void Swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}
//向上调整算法
void AdjustUp(HPDataType* a, int child)
{
	//父节点
	int 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;
		}
	}
}

//插入
void HeapPush(Heap* php, HPDataType x)
{
	assert(php);
	//插入数据的过程
	//容量不够则需要扩容
	//判断空间是否不足
	if (php->size == php->capacity)
	{
		int newcapacity = php->capacity == 0 ? 4 : 2 * php->capacity;
		//为堆开辟空间
		HPDataType* tmp = (HPDataType*)realloc(php->a, sizeof(HPDataType) * newcapacity);
		if (tmp == NULL)
		{
			perror("realloc fail");
			return;
		}
		php->capacity = newcapacity;
		php->a = tmp;
	}
	//插入数据
	php->a[php->size] = x;
	php->size++;
	//向上调整
	AdjustUp(php->a, php->size - 1);
}

//向下调整
void AdjustDown(HPDataType* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;

	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//删除
void HeapPop(Heap* php)
{
	assert(php);
	//判断堆是否为空
	assert(!HeapEmpty(php));
	//交换堆顶的数据和最后的数据
	Swap(&php->a[0], &php->a[php->size - 1]);
	//删除最后的数据
	php->size--;
	//向下调整
	AdjustDown(php->a, php->size, 0);
}

//判空
bool HeapEmpty(Heap* php)
{
	assert(php);
	return php->size == 0;
}

//获取堆顶元素
HPDataType HeapTop(Heap* php)
{
	assert(php);
	//判断堆是否为空
	assert(!HeapEmpty(php));
	return php->a[0];
}

//堆排序
void HeapSort(int* a, int n)
{
	//建堆
	Heap hp;
	HeapInit(&hp);
	//将数组先插入到堆中实现堆中的大小堆排序
	for (int i = 0; i < n; i++)
	{
		HeapPush(&hp, a[i]);
	}
	//再将堆中的数据拷贝到数组中
	int i = 0;
	while (!HeapEmpty(&hp))
	{
		//保存堆顶元素
		int top = HeapTop(&hp);
		//拷贝
		a[i++] = top;
		HeapPop(&hp);
	}
	HeapDestroy(&hp);
}

int main()
{
	int a[] = { 5,6,8,9,7,4,5,2,3,6 };
	int sz = sizeof(a) / sizeof(int);
	HeapSort(a, sz);
	return 0;
}

我们在这里建的是小堆，所以是排成了升序的状态，建大堆只要将向上调整和向下调整的小于号换成大于号即可。

这种算法有点弊端：

1. 必须先要有一个堆，太麻烦。

2. 将数组的数据拷贝至堆，又将堆的数据拷贝至数组，空间复杂度上面代价有点大。

但是这种算法的时间复杂度也是不错的，在前面我们讲堆的时候提到过向上调整算法和向下调整算法，这两种算法的时间复杂度都是O(logN)，那么在这个堆排序的算法中的时间复杂度加上遍历数组的时间复杂度合起来为O(N*logN)。

1.2向上调整算法建堆

在使用向上调整算法和向下调整算法的时候如果要达到降序的目的应该建大堆还是小堆？如果要达到升序的目的应该建大堆还是小堆？

我们在这里来思考一下：

按照以往的思路：要排成降序需要建大堆，这样就保证了最大的一个在堆顶，然后将除了堆顶剩下的数据看作一个堆，再找到次大的，这时就面临两个问题：

1. 将剩下的数据看作一个堆时又需要重新建堆，代价有点大。

2. 如果将剩下的数据重新建堆，那么它们原来的父子关系就乱套了，从之前的兄弟变成父子或许有点扯淡。

那么我们就来换一种思路，这种思路和删除数据时的思路一样，我们要排成降序我们就建小堆，那么这时堆顶的数据就是最小的，然后将堆顶的数据和最后一个数据交换，这时堆的最后一个数据就是最小的，此时，就不需要将最后一个数据看作堆中的数据，然后再对剩余数据进行向下调整，再找出次小的，再交换至倒数第二个位置......这样子依次类推，直到全部找出来。同样的，要排成升序就建大堆，找出最大的交换，再找次大的，再交换......依次类推同样也可以完成升序。

这里还有需要注意的一个点，我们要从哪里开始进行向上调整建堆？之前说过向上调整算法调整的节点的上面必须是一个堆，因此我们需要从第一个结点开始进行向上调整建堆，因为第一个结点就是一个堆，所以我们将第一个结点看作堆，然后从第二个位置开始插入，前面的结点是堆，符合。

代码演示：
//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向上调整算法
void AdjustUp(int* a, int child)
{
	//父节点
	int 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;
		}
	}
}

//向下调整
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;

	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//建堆--向上调整算法建堆
	//模拟的是一个插入堆的过程
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		//交换堆顶和最后一个数据的位置
		Swap(&a[0], &a[end]);
		//向下调整，找次小的
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 5,6,8,9,7,4,5,2,3,6 };
	int sz = sizeof(a) / sizeof(int);
	HeapSort(a, sz);
	return 0;
}
我们在这里建的是小堆，所以是排成了降序的状态，建大堆只要将向上调整和向下调整的小于号换成大于号即可。

1.3向下调整算法建堆

排降序建小堆，排升序建大堆，当我们使用向上调整算法来建堆实现堆排序时，需要用到向上调整算法和向下调整算法，这个有点太麻烦，那既然在交换数据之后要进行向下调整，那不妨直接使用向下调整算法来直接建堆。

向下调整算法使用的前提是向下调整的结点的下面必须是堆，我们不妨画图来观察一下：

我们知道一个叶子节点本身就是大堆或者小堆，因此我们可以在叶子节点上面下下功夫。

向下调整算法的下面必须是堆：
而叶子节点恰好又是堆，那么叶子节点就可以不用处理，那么我们就可以倒着来进行建堆，从最后一个非叶子节点开始调整（倒数第一个叶子节点的父亲开始调整）。根据孩子与父亲的关系找到父亲然后调整建堆，由于叶子节点本身就是堆，从它的父亲开始调整也符合向下调整算法的逻辑。

代码演示：
//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;

	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

void HeapSort(int* a, int n)
{
	//建堆--向下调整算法建堆

	for (int i = ((n - 1) - 1) / 2; i >= 0; --i)
	{//       这里的n-1表示最后一个叶子节点
		//       最后一个叶子节点的父亲就是：
		//           （n-1）-1 /2；
		AdjustDown(a, n, i);
	}

	int end = n - 1;
	while (end > 0)
	{
		//交换堆顶和最后一个数据的位置
		Swap(&a[0], &a[end]);
		//向下调整，找次小的
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 5,6,8,9,7,4,5,2,3,6 };
	int sz = sizeof(a) / sizeof(int);
	HeapSort(a, sz);
	return 0;
}

2.算法时间复杂度

一个算法的好与坏取决与它的时间和空间，那么对于向上调整建堆和向下调整建堆哪种方法的时间复杂度更优呢？我们可以一一来计算一下。

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

假设二叉树的高度为h，总结点个数为N

第1层: 有2^0个节点，需要向下挪动h-1次
第2层: 有2^1个节点，需要向下挪动h-2次
第3层: 有2^2个节点，需要向下挪动h-3次
......
第h-1层: 有2^(h-2)个节点，需要向下挪动1次
第h层: 有2^(h-1)个节点，需要向下挪动0次

总共合计需要挪动：

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

使用错位相减法：

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

-

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

F(h) = 2^h - 1 - h

这棵树的中的节点的个数为N = 2^h-1 ==> h = log(N+1)

F(N) = N - log(N+1)

因此向下调整算法的时间复杂度为O(N)

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

向上调整很明显就是一个多乘多的问题，单单只看最后一层，节点越多，调整的次数越多，那这就完蛋了，向下调整算法最后一层的节点时不需要调整的，那这就很明显了，向下调整算法明显优势于向上调整算法，那么到底能快多少呢？我们一起来计算一下：

假设二叉树的高度为h，总结点个数为N

第1层: 有2^0个节点，需要向下挪动0次
第2层: 有2^1个节点，需要向下挪动1次
第3层: 有2^2个节点，需要向下挪动2次
......
第h-1层: 有2^(h-2)个节点，需要向下挪动h-2次
第h层: 有2^(h-1)个节点，需要向下挪动h-1次

总共合计需要挪动：

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

使用错位相减法：

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

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

这棵树的中的节点的个数为N = 2^h-1 ==> h = log(N+1)

F(N) = (N + 1) * (log(N + 1) - 2) + 2

因此向上调整算法的时间复杂度为O(N * logN)

3.堆排序的时间复杂度

计算出了向下调整建堆的时间复杂度，我们再来看看堆排序算法的整体的时间复杂度。

这时我们就要计算筛选数据操作时的交换数据和向下调整的时间复杂度：

这里为什么最上面的反而不用向下调整那么多次了，是因为在调整上面的数据时，下面的数据已经是一个堆了，所以筛选数据的过程就和向上调整建堆的时间复杂度一样。

时间复杂度是O(N * logN )

那么再加上向下调整建堆的时间复杂度就是O(N) + O(N * logN)

所以整个堆排序算法的时间复杂度为O（N * logN）

4.完整堆排序代码

//交换函数
void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

//向下调整
void AdjustDown(int* a, int n, int parent)
{
	//假设左孩子为左右孩子中最小的节点
	int child = parent * 2 + 1;

	while (child < n)  //当交换到最后一个孩子节点就停止
	{
		if (child + 1 < n  //判断是否存在右孩子
			&& a[child + 1] < a[child]) //判断假设的左孩子是否为最小的孩子
		{
			child++;   //若不符合就转化为右孩子
		}
		//判断孩子和父亲的大小关系
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			//更新父亲和孩子节点
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//O(N * logN)
void HeapSort(int* a, int n)
{
	//建堆--向下调整算法建堆
	//时间复杂度为O(N)
	for (int i = ((n - 1) - 1) / 2; i >= 0; --i)
	{//       这里的n-1表示最后一个叶子节点
		//       最后一个叶子节点的父亲就是：
		//           （n-1）-1/2；
		AdjustDown(a, n, i);
	}

	//O(N * logN)
	int end = n - 1;
	while (end > 0)
	{
		//交换堆顶和最后一个数据的位置
		Swap(&a[0], &a[end]);
		//向下调整，找次小的
		AdjustDown(a, end, 0);
		end--;
	}
}

int main()
{
	int a[] = { 5,6,8,9,7,4,5,2,3,6 };
	int sz = sizeof(a) / sizeof(int);
	HeapSort(a, sz);
	return 0;
}