初阶数据结构（C语言实现）——5.3 堆的应用（1）——堆排序

初阶数据结构（C语言实现）——5.2 二叉树的顺序结构及堆的实现
初阶数据结构（C语言实现）——5.1二叉树基础概念

1 堆的应用

1.1 堆排序

1.1.1 思路

堆排序即利用堆的思想来进行排序，总共分为两个步骤：

1. 建堆
   升序：建大堆
   降序：建小堆
2. 利用堆删除思想来进行排序
   建堆和堆删除中都用到了向下调整，因此掌握了向下调整，就可以完成堆排序。
   

1.1.2 代码实现

void swap(HPDataType* p1, HPDataType* p2)
{
	HPDataType x = *p1;
	*p1 = *p2;
	*p2 = x;
}

 void AdjustUp(HPDataType* a, int child)
{
	int parent = (child - 1) / 2;//根据孩子位置，计算父亲位置
	while (child > 0)//child = 0,说明parent不存在了,已经到堆顶了
	{
		if (a[child] > a[parent]) //当孩子大小大于父亲大小的时候就交换
		{
			swap(&a[child], &a[parent]);//因为其他地方也要用到交换，封装了一个交换函数
			child = parent; //现在把父亲的值给孩子。
			parent = (child - 1) / 2;//继续计算现在节点的父亲结点，
		}
		else//孩子<=父亲 没必要往上走，直接break就行。		
		{
			break;
		}
	}
}
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+1<n放前面，否则后面a[child+1]就越界了！
		{
			++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)//参数：数组和数据个数
{
	 //建堆，方法1：向上调整堆 //模拟的是插入数据的过程
	 for (int i = 1; i < n; ++i)
	 {
		 AdjustUp(a, i);
	 }
	 //建堆，方法2：向下调整堆
	 for (int i = 1; i < n; ++i)
	 {
		 AdjustDown(a, n , i);
	 }


	 int end = n - 1;
	 while (end > 0)
	 {
		 swap(&a[end], &a [0]);
		 AdjustDown(a, end, 0);
		 --end;

	 }
}

1.2 建堆的时间复杂度

1.2.1 向下调整

因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：

因此：向下建堆的时间复杂度为O(N)。

1.2.1 向上调整

因此向上建堆的时间复杂度是N*log_n

1.2.3 结论

向下调整时间复杂度更小，更优，所以建堆使用的是向下调整