堆排序（c语言）

前言

堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

一.什么是堆

堆它分两种结构逻辑结构和物理结构

逻辑结构是完全二叉树

物理结构是数组

堆还有两种特征

1.结构性：用数组表示的完全二叉树。

2.有序性：任一结点的根要大于或小于子节点：称为大堆小堆

通过向标建立父子节点的关系

左孩子（默认为child）

leftchild=parent*2+1
rightchild=parent*2+2
parent=(child-1)/2

二.向下调整算法

要想实现堆排序，首先必须知道什么是向下调整算法。

前提：左右子树都是小堆或者大堆

思路：从根节点开始，选出左右孩子中小的那一个，跟父亲比较，如果父亲小就交换，然后再往下调调到叶子节点结束

void AdjustDwon(int* a, int n, int root)
{
	int parent = root;
	 //默认左孩子为child
	int child = parent * 2 + 1;
	//不能越界，所以要小于n，因为下标最高到n-1，随意当迟来的当n是出while语句
	while (child < n)
	{
		//选出左右孩子中小的那一个
		//child + 1 < n如果出现只有左孩子没有右孩子的节点，就会存在越界现象
		if (child + 1 < n && a[child + 1] < a[child])
			child += 1;
		//如果小就交换，默认排升序
		if (a[child] < a[parent])
		{
			Swap(&a[child], &a[parent]);
			parent = child;
			child = parent * 2 + 1;
		}
		//如果不存在大小交换，说明已经排完了
		else
		{
			break;
		}


	}

三.堆排序的创建

建堆

就是先把数组转化为堆

利用向下调整算法去建立堆

思路：叶子是不用排的，从倒数最后一个非叶子的父亲开始调

	//int i = (n - 1 - 1)父亲公式
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}

思考：排一个升序是建大堆还是小堆

如果是排小堆的化，每次从头顶拿出数据，就要打乱一个堆，又要把一个堆重新排，他的时间复杂度就为O（N*N),所以要用大堆排，第一个和最后一个交换，把它不看作堆里面的前N -1个数向下调整，选出最大的数再跟倒数第二个位置交换这样它的时间复杂度就为O（N*logN)。

void Heapsort(int* a, int n);
{
	//int i = (n - 1 - 1)父亲公式
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDwon(a, n, i);
	}
	
	int end = n - 1;
	while (end > 0)
	{
		Swap(&a[0], &a[end]);
		AdjustDwon(a, end, 0);
		end--;
	}

}

四.堆的时间复杂度

总结

  堆是一种很好做调整的结构，在算法题里面使用频度很高。常用于想知道最大值或最小值的情况，比如优先级队列，作业调度等场景。