【数据结构取经之路】建堆&堆排序

目录

引言

建堆的两种方法

一、向上调整建堆

二、向下调整建堆

两种建堆方式的性能比较

堆排序

堆排序的思想

堆排序的时间复杂度

堆排序的空间复杂度

堆排序代码

---

 

引言

首先，介绍一下本次的主人公——堆。堆是一种数据结构，在逻辑上是一棵二叉树，在物理上是一维数组。堆，可以作为堆排序的前提，还可以有效解决TopK问题。学会建堆是学会堆排序的必要前提，因次，在讲堆排序之前，我们先聊聊如何建堆。

建堆的两种方法

不管是向上调整算法还是向下调整算法，都是有一个重要前提的。如果要调成小堆，那么在插入数据之前，要保证原有的二叉树是小堆：如果要调成大堆，要保证在插入数据之前，原有的二叉树是大堆。

请看上图，预期是插入77后调为大堆。首先的明白一点，77只会沿着它的祖宗往上调直到根，也就是图中的红色线路，右边是调整完以后得到的二叉树，它根本不是大堆，原因就在于插入77之前原有的二叉树不是大堆，调完后，只有红色线路的满足大堆的大小关系，但其他部分并不满足。所以才会要求，插入数据前，原有二叉树是大堆。预期是调为小堆也同理。

一、向上调整建堆

向上调整建堆就是在模拟向堆插入数据的过程。下面将以建大堆为例。

第一个数据插入时，堆里只有一个元素，不需要调整，而且，单个结点既可以认为是大堆，也可以认为是小堆，满足向上调整的前提。当插入19时，因为19 > 11,所以需要向上调整，确保是大堆，插入9时，9 < 19,不需要调整 ，插入再多的数据也同理。因为堆的底层是用数组实现的，所以我们可以通过控制数组的下标来控制二叉树，即控制堆。请看代码：

#include 
 
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	printf("\n");
}
 
void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = 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 BuildHeap(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
}
 
int main()
{
	int a[] = { 5,1,8,5,};
	int n = sizeof(a) / sizeof(int);
	Print(a, n);
	BuildHeap(a, n);
	Print(a, n);
	return 0;
}
 

二、向下调整建堆

以调成小堆为例。

如上图，52要向下调整建小堆的前提是，红圈内必须是小堆，即它的左右子树必须是小堆。 同时，还需注意，52是要和它较小的孩子比较的，如果它比它较小的孩子还小，就不用换下来，反之，则需要交换，直到不满足交换条件。

代码：

#include 
 
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	printf("\n");
}
 
void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = tmp;
}
 
void AdjustDown(int* a, int n, int parent)
{
	//假设左右孩子中小的那个为左孩子，如果假设错误，下面会修正
	int child = parent * 2 + 1;
 
	while (child < n)
	{
        //child + 1 < 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 BuildHeap(int* a, int n)
{
	//从最后一个节点的父亲开始向下调整
	for (int i = (n - 2) / 2; i >= 0; i--)AdjustDown(a, n, i);
}
 
int main()
{
	int a[] = { 4,1,7,4,7,9,0,1 };
	int n = sizeof(a) / sizeof(int);
	Print(a, n);
	BuildHeap(a, n);
	Print(a, n);
	return 0;
}

两种建堆方式的性能比较

上图的满二叉树一共有16个结点，其中，最后一层占了一半，倒数第二层占了四分之一，其他的满二叉树也是这种情况。 

向上调整算法：假设二叉高度为h，除去第一层不用向上调整，在最坏情况下，其余各层的每一个节点都需要向上调整。因为向上调整的次数与层数有关，所以设前h层需要调整次数的函数为F(h).

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

h = log(N + 1)  ==> N = 2^h - 1 

得到近似值 F(N) = N*logN

所以，向上调整建堆的时间复杂度为：O(n*logn)  

向下调整算法：

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

h = log(N + 1)  ==> N = 2^h - 1 

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

取近似值：F(N) = N

所以，向下调整建堆的时间复杂度为：O(n)

通过分析，我们可以看到，向上调整算法，节点数量越多，调整次数(层数越深)越多；向下调整算法，节点数量越多，调整次数越少。从这一角度定性分析，也可以得出向下调整算法较优的结论。

堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。

堆排序的思想

以上图为例，将堆顶元素与最后一个元素交换，此时，最大的元素已经被选出并放到了数组的尾部，接着，再调用向下调整算法，对0到n-1下标的元素进行向下调整，调成大堆后，继续将堆顶元素交换到尾部n-1的位置，此时选出了次大的数……重复上述调整交换的操作，直到只有一个元素。

升序建大堆，降序建小堆。下面以大堆为例说明原因。

大堆，每次均把堆顶的元素交换到了尾部。第一次交换时，把最大的交换到了下标为n-1的位置，第二次交换时，把次大的交换到了下标为n-2的位置，这样，待排完序后，数组就成了升序。归根结底，是因为有交换这一操作。降序用小堆同理。 

堆排序的时间复杂度

O(n*logn)

堆排序的空间复杂度

堆排序是一种原地排序算法，不需要额外的空间来存储数据，所以它的空间复杂度为O(1)。

堆排序代码

#include 
 
void Print(int* a, int n)
{
	for (int i = 0; i < n; i++) printf("%d ", a[i]);
	printf("\n");
}
 
void Swap(int* px, int* py)
{
	int tmp = *px;
	*px = *py;
	*py = 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 = 2 * parent + 1;
		}
		else
		{
			break;
		}
	}
}
 
void HeapSort(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[end], &a[0]);
		AdjustDown(a, end, 0);
		end--;
	}
}
 
int main()
{
	int a[] = { 4,1,8,4,6,0,1,7,3,9 };
	int n = sizeof(a) / sizeof(int);
	Print(a, n);
	HeapSort(a, n);
	Print(a,n);
	return 0;
}