C语言实现堆排序

目录

什么是堆，堆排序

1.堆

堆排序思路

实例C语言实现堆排给数组排序 

1.建堆：

向下调整建堆法

 2.选数

整体代码

 

---

什么是堆，堆排序 1.堆

堆是一种特殊的二叉树数据结构，分为大根堆与小根堆，大根堆即二叉树即其子树都满足：

根节点的值大于子树根节点的值。小根堆则相反。

如图

堆排序就是利用堆的性质将数据排序。

堆排序思路

堆排序的思路就是:

1.先将所有数据整理成堆

2.从堆顶将最值拿出来 

3如此循环 *** 作 直到堆中数据为0。

目标时间杂度：O(N*logN)

空间复杂度：O(1) 

实例C语言实现堆排给数组排序  1.建堆：

要实现O(1)的空间复杂度，就不能额外开辟一块空间来建堆，而是直接在数组中建立堆结构，也就是直接将数组中的数据整理成一个堆。

向下调整建堆法

若 一颗二叉树满足条件：它的左右子树皆为大/小根堆 ，那么便可以把它的根向下调换到合适位置，整颗树也成了大/小根堆。

我们将数组视为二叉树:他们父节点与孩子节点的下标就满足公式：

1. parent=(child-1)/2

2. leftchild=parent*2+1

3.rightchild=parent*2+2

那么我们堆排序的第一步就是:将所有数据整理成堆

方法：从最后一个节点的父亲节点开始向下调整每一棵树

如图：把一个数组{1，2，3，4，5，6，7}调整为大根堆。

向下调整代码：

void _AdjustDown(int* arr, int parent, int end) {
	int child = parent * 2 + 1;//要调整树 根节点的左孩子
	while (child <= end) {//只要还能向下调整便进入循环
		if (child + 1 <= end && arr[child + 1] > arr[child])
			child++;//判断是否有右孩子，以及右孩子是否大于左孩子；
		if (arr[child] > arr[parent]) {//再比较根节点与较大孩子，看是否需要向下交换；
			Swap(arr + parent, arr + child);
			parent = child;//交换后调整孩子节点与根节点
			child = child * 2 + 1;
		}
		else//如果已经满足大根堆的条件，即左右孩子都小于根，则退出循环
			break;
	}
}

 调整完后的大根堆：

 2.选数

将所有数据整理成堆以后，最大/小值就到了堆顶，我们就可以反复利用这个性质选出最值。再建堆再选出最值...如此循环实现排序。

代码及其思路：

每一步的步骤都写在注释中了

	//所有数据建成堆后
	for ( n-=1; n > 0; ) {
	//将堆顶（最大的元素）堆中最后一个元素交换（这样可以不破坏堆原有结构，即左右子树皆是堆）
		Swap(arr, arr + n--);//堆顶的元素就到了应在的位置，故n--将堆的大小减1.
	//将交换后的元素像下调整。
		_AdjustDown(arr, 0, n);
	}//循环堆中只剩一个元素

整体代码

void _AdjustDown(int* arr, int parent, int end) {
	int child = parent * 2 + 1;//要调整树 根节点的左孩子
	while (child <= end) {//只要还能向下调整便进入循环
		if (child + 1 <= end && arr[child + 1] > arr[child])
			child++;//判断是否有右孩子，以及右孩子是否大于左孩子；
		if (arr[child] > arr[parent]) {//再比较根节点与较大孩子，看是否需要向下交换；
			Swap(arr + parent, arr + child);
			parent = child;//交换后调整孩子节点与根节点
			child = child * 2 + 1;
		}
		else//如果已经满足大根堆的条件，即左右孩子都小于根，则退出循环
			break;
	}
}

void HeapSort(int* arr, int n)
{
	//从最后一个节点的父亲节点开始向下调整每一棵树
	for (int parent = (n - 1 - 1) >> 1; parent >= 0; parent--)
		_AdjustDown(arr, parent, n - 1);
	//所有数据建成堆后
	for ( n-=1; n > 0; ) {
	//将堆顶（最大的元素）堆中最后一个元素交换（这样可以不破坏堆原有结构，即左右子树皆是堆）
		Swap(arr, arr + n--);//堆顶的元素就到了应在的位置，故n--将堆的大小减1.
	//将交换后的元素像下调整。
		_AdjustDown(arr, 0, n);
	}//循环堆中只剩一个元素
}