【排序算法】—— 堆排序

一、堆的概念

​ 堆（heap）：一个完全二叉树，每个节点都比子节点的值大或小

​ 大根堆：每个节点的值都比其子节点大

​ 小根堆：每个节点的值都比其子节点小

二、堆的建立

1. 向上调整

​ 小根堆向上调整

1. 将被调整的数值与其父节点比较，若是小于父节点，则与父节点交换
2. 若子节点下标为child，父节点下标为(child - 1) / 2
3. 当子节点大于父节点时，或者当子节点已经为堆顶时，停止比较

代码实现：

typedef int HPDataType;	//HPDataType是堆存储的数据的类型，这里是int型

void AdjustUp(HPDataType* data, int child)
{
	int parent = 0;
	while (child > 0)
	{
		parent = (child - 1) / 2;
		if (data[child] < data[parent])
		{
			Swap(&data[child], &data[parent]);
			child = parent;
		}
		else
		{
			break;
		}
	}
}

​ 大根堆向上调整

• 将被调整的数值与父节点比较，若是大于父节点，则与父节点交换，将小根堆比较条件改为大于即可

if (data[child] > data[parent])
    ...

2. 向下调整

​ 小根堆向下调整

1. 将被调整的数值与其最小的子节点比较，若是大于最小的子节点，则与该子节点交换
2. 若父节点下标为parent，左子节点下标为 parent * 2 + 1，右子节点的下标为 parent * 2 + 2
3. 获取最小的子节点时，可以先将左子节点作为最小节点，再与右子节点比较，若是大于右子节点，则将左子节点下标加1得到右子节点下标
4. 再循环体内比较左右子节点之前，要先判断右子节点存在，防止堆最后一个节点是左子节点造成越界访问
5. 当子节点小于父节点时，或者当子节点超过堆的范围时，停止比较

代码实现：

void AdjustDown(HPDataType* data, int size, int parent)
{
	int minchild = parent * 2 + 1;
	while (minchild < size)
	{
        //比较左右子节点
		if (minchild + 1 < size && data[minchild] > data[minchild + 1])
		{
			minchild++;
		}
		
		if (data[minchild] < data[parent])
		{
			Swap(&data[minchild], &data[parent]);
			parent = minchild;
			minchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

​

​ 大根堆向下调整

1. 将被调整的数值与其最大的子节点比较，若是小于最大的子节点，则与该子节点交换
2. 将小根堆向下调整时左右子节点的比较条件和父节点与子节点的比较改为大于即可

if (maxchild + 1 < size && data[maxchild] < data[maxchild + 1])
    ...
if (data[maxchild] > data[parent])
    ...

三、堆排序

1. 堆排序的步骤

​ 堆排序的步骤可以分为2个部分

1. 建堆：将数组每一位都进行调整，使其成为一个堆
2. 选数：利用堆的特性，最大值或最小值位于堆顶，依次选择出堆的最大最小值，进行数组的排序

1.1 建堆

​ 将数组构建成堆时，可以使用向上调整或向下调整

向上调整

​ 将数组第1个元素作为一个堆，从第2个元素到第n-1个元素依次进行向上调整。

int i = 0;
for (i=1; i<n; i++)
{
    AdjustUp(arr, i);	//从1到n-1进行调整
}

​ 每一次向上调整的时间复杂度为$O(lo{g}_{2}n)$

​ 所以使用向上调整建好堆的时间复杂度为$O(nlo{g}_{2}n)$

向下调整

1. 向下调整是从后往前调整，先将后面构成堆，再调整上面的节点
2. 以叶子节点作为根进行向下调整是完全没有必要的，叶子节点没有子节点，所以对最后一个叶子节点的父节点开始向下调整
3. 最后一个节点下标是n-1，它的父节点为 (n-1-1) / 2

int i = 0;
for (i=(n-2)/2; i>=0; i--)
{
    AdjustDown(arr, n, i);	//从 (n-2)/2 到 0 进行调整
}

​ 时间复杂度计算

则需要移动节点的步数为

$$T_n=2^0\times (h-1)+2^1\times (h-2)+2^2\times (h-3)+...+2^{h-2}\times 1$$

这是一个等差数列乘以一个等比数列，使用裂项相消法进行化简

$$2T_n=2^1\times (h-1)+2^2\times (h-2)+2^3\times (h-3)+...+2^{h-1}\times 1$$

$$2T_n-T_n=-h+2^0+2^1+2^2+...+2^{h-1}+2^{h-2}\times 1$$

$$T_n=-h+2^h-1$$

因为 $n=2^h-1$，$h=lo{g}_2(n+1)$

$$T_n=n-lo{g}_2(n+1)\approx n$$

向下调整的时间复杂度为 $O(n)$

因此，堆排序都是使用向下调整的方式

1.2 选数

​ 进行选数时，我们通过大根堆选出最大的数，利用小根堆选出最小的数

升序排序

​ 利用小根堆排序

1. 使用小根堆选出最小的数，放在数组的第一个位置，依次选出进行排序
2. 当堆顶被移除时，堆的结构会被破坏，使用第二个数作为堆顶时，要重新对后面的每一个数进行调整

​ 利用大根堆排序

1. 使用大根堆选出最大的数，放在数组的最后一个位置，依次选出进行排序
2. 将堆顶和最后一个数交换
3. 然后将新堆顶向下调整，形成堆
4. 向下调整时，注意交换后的最后位置不在新堆里，所以要下标要减一
5. 没有对堆结构造成破坏，不用对每个数都调整

​ 所以升序排序是使用大根堆选出最大数放到最后一个位置的方式进行排序

for (i=n-1; i>0; i--)	//从最后一个位置开始交换并调整
{
    Swap(&arr[0], &arr[i]);
    AdjustDown(arr, i-1, 0);	//此处为大根堆向下调整方式
}

降序排序

1. 利用大根堆选出最大数放在第一个位置依然会破坏堆结构，所以不使用
2. 使用小根堆选出最小数放在最后一个位置的方式进行排序

for (i=n-1; i>0; i--)
{
    Swap(&arr[0], &arr[i]);
    AdjustDown(arr, i-1, 0);	//此处为小根堆向下调整方式
}

3. 代码实现

​ 以下为整型数组升序排序的实现

typedef int HPDataType;	//堆存储的数据的类型

//交换数据
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}

//向下调整（大根堆）
void AdjustDown(HPDataType* data, int size, int parent)
{
	int maxchild = parent * 2 + 1;
	while (maxchild < size)
	{
        //比较左右子节点
		if (maxchild + 1 < size && data[maxchild] < data[maxchild + 1])
		{
			maxchild++;
		}
		
		if (data[maxchild] > data[parent])
		{
			Swap(&data[maxchild], &data[parent]);
			parent = maxchild;
			maxchild = parent * 2 + 1;
		}
		else
		{
			break;
		}
	}
}

//堆排序
void HeapSort(int arr, int n)
{
    int i = 0;
    
    //建堆
    for (i=(n-2)/2; i>=0; i--)
    {
        AdjustDown(arr, n, i);
    }
    
    //选数
    for (i=n-1; i>0; i--)
    {
        Swap(&arr[0], arr[i]);
        AdjustDwon(arr, i-1, 0);
    }
}