当前位置：首页 > article >正文

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

article 2025/3/14 13:46:58

1 堆的应用

1.1 堆排序

1.1.1 思路

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

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

在这里插入图片描述

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;

	 }
}