堆排序详细理解

目录

一、前备知识

二、建堆

2.2.1 向上调整算法建堆

2.2.2 向下调整算法建堆

三、排序

3.1 常见问题 

3.2 思路

3.3 源码

---

一、前备知识

详细图解请点击：二叉树的顺序实现-堆-CSDN博客

本文只附上向上/向下调整算法的源码

//交换
void Swap(int* p, int* q)
{
	int tmp = *p;
	*p = *q;
	*q = 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[parent] > a[child])
		{
			Swap(&a[parent], &a[child]);
			parent = child;
			child = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}
//向上调整算法
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;
		}
	}
}

二、建堆

堆排序堆排序，先有堆才能排序，所以排序的第一步是要将一个一般的数组建成堆。

注：由于建大堆还是小堆仅仅取决于自定的大小于号，本文下述建堆都以小堆为例

2.2.1 向上调整算法建堆

思路：

1. 单一的一个结点可以看成一个堆
2. 后续的所有结点都可以看作是插入结点

所以只需要循环插入所有后续结点即可

void BuildHeap1(int* a, int n)
{
	//把根节点看作是堆，剩下的结点看作插入结点，开始依次插入
	for (int i = 1; i < n; i++)
	{
		AdjustUp(a, i);
	}
}

2.2.2 向下调整算法建堆

错误思路：

向下调整算法要求左右子树必须为大/小堆，所以从根节点开始结点开始建堆的做法是错误的

正确思路：

上文说：单一的一个结点可以看成一个堆。所以从最后一个叶子节点的父节点开始向下调整，不断循环所有父节点，就可以保证他的左右子树都是堆。

void BuildHeap2(int* a, int n)
{
	//从最后一个叶子结点的父结点开始调
	for (int i = ((n - 1) - 1) / 2; i >= 0; i--)
	{
		AdjustDown(a, n, i);
	}
}

三、排序

3.1 常见问题 

• 为什么建堆后依然还要排序？

        大堆/小堆的定义注定了堆仅仅能保证父节点大于孩子结点，无法保证孩子结点按照大于/小于的次序严格排列！！！

• 升序建小堆，降序建大堆的思路是否可行？

1. 升序建小堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建小堆，选出第二小的数，不断重复上述过程。若用向上调整算法可行但时间复杂度太高，若使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。
2. 降序建大堆：首先对 n 个数建小堆，选出最小的数，接着对剩下的 n-1 个数建大堆，选出第二大的数，不断重复上述过程。使用向下调整算法时，对n-1个调整就会发现：原先的孩子父亲关系全乱，不可行。

3.2 思路

1. 本质上是堆删除的思路。利用堆的特性，无论是大堆还是小堆，根节点的值一定是最大/小的数。这样每进行一次调整，就会选择出最小/大，次小/大......便可以实现排序。
2. 为了防止出现父子关系乱序的问题，将每次找到的最值放在堆的末位置，对前n-1个元素进行向下调整，便可以完美解决排序问题
3. 由此可以总结：升序建大堆，降序建小堆。

由此，我们可以归纳出堆排序算法的步骤：

1. 把无序数组构建成二叉堆。

2. 循环删除堆顶元素，移到数组尾部，调节堆产生新的堆顶。

3.3 源码

//降序建小堆
void HeapSortDown(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--;					// 调整前n-1个元素
	}
}