数据结构——堆排序

目录

引言

堆排序

1.算法思想

2.算法步骤

3.代码实现

3.1 构建堆

(1)小堆

(2)大堆

3.2 交换与调整

3.3 重复上述过程

4.复杂度分析

5.完整代码

5.1算法实现代码

5.2 示例

6.堆排序的优势

结束语

引言

本篇博客，我们将利用堆结构实现的高效排序算法，深入理解其原理与应用。

如果还不了解堆这一数据结构，可以先看看这篇博客：数据结构——堆

堆排序

1.算法思想

堆排序（Heap Sort）是一种基于堆数据结构实现的排序算法。利用堆这种数据结构的高效性，通过构建和调整堆来实现排序，是一种性能优秀的排序算法。

堆排序的核心思想是将待排序的元素构建成一个最大堆或最小堆，然后依次将堆顶元素与堆中最后一个元素交换，并重新调整堆，使剩余元素重新满足堆的性质。重复这一过程直到所有元素都被取出，最终得到了一个有序的序列。

2.算法步骤

堆排序的核心思想确实是将待排序的元素构建成一个最大堆（对于升序排序）或最小堆（对于降序排序），然后依次执行以下步骤：

(1)构建堆：首先，将待排序的序列通过一系列调整操作构建成一个最大堆（或最小堆）。在构建过程中，从最后一个非叶子节点开始，向上进行堆调整（Heapify），确保每个子树都满足堆的性质。

(2)交换堆顶元素与堆尾元素：将堆顶元素（即当前序列中的最大或最小值）与堆的最后一个元素进行交换。这样，堆顶元素就被放到了它在排序后序列中正确的位置上。

(3)重新调整堆：将交换后的堆（此时最后一个元素是已知的最大或最小值，因此不再参与后续的堆操作）的大小减一，然后对新的堆顶元素执行堆调整操作，以恢复堆的性质。这一步是为了确保剩余的元素仍然构成一个最大堆（或最小堆）。

(4)重复步骤2和3：不断重复交换堆顶元素与堆尾元素，并重新调整堆的过程，直到堆的大小减至1。此时，整个序列就被排序完成了。

堆排序的实现基于上面的步骤。

3.代码实现

3.1 构建堆

借助建堆算法，降序建小堆，升序建大堆，选择向上或者向下调整算法。

向上调整建堆和向下调整建堆是构建堆的两种主要方法，它们各有特点，但都能达到同样的目的：将一组元素组织成一个堆结构。

向上调整建堆：从最后一个非根节点开始向前遍历，对每个节点进行上浮操作，确保每个节点都满足堆的性质，即父节点的值大于等于（或小于等于）其子节点的值。

向下调整建堆：从最后一个非叶子节点开始向上遍历到根节点，对每个节点执行下沉操作，通过比较和交换，确保每个节点都满足堆的性质，从而构建出堆结构。

向下调整算法优于向上调整，我们在这里选择向下调整算法。

(1)小堆

// 建小堆
void AdjustDownSmall(int* arr, int n, int parent)
{
	// 假设左孩子小
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 如果右孩子存在且比左孩子小，则选择右孩子进行比较
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			++child;
		}
		// 如果选中的孩子节点小于父节点，则交换它们，并继续向下调整  
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); // 交换父节点和孩子节点  
			parent = child;			// 更新父节点为原来的孩子节点  
			child = parent * 2 + 1; // 更新child为新的父节点的左孩子索引  
		}
		else
		{
			// 如果孩子节点不小于父节点，则无需继续调整，跳出循环
			break;
		}
	}
}

(2)大堆

// 建大堆
void AdjustDownLarge(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 如果右孩子存在且比左孩子大，则选择右孩子进行比较  
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			++child; // 更新child为右孩子的索引  
		}
		// 如果选中的孩子节点大于父节点，则交换它们，并继续向下调整  
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]); // 交换父节点和孩子节点  
			parent = child;			// 更新父节点为原来的孩子节点  
			child = parent * 2 + 1; // 更新child为新的父节点的左孩子索引  
		}
		else
		{
			// 如果孩子节点不大于父节点，则无需继续调整，跳出循环  
			break;
		}
	}
}

3.2 交换与调整

建完堆之后，就到排序
我们在这里以降序为例子：

每次将堆顶与堆尾数据交换（相当于将当前的最小值挪到最后），然后堆尾数据伪删除（有效数据个数--，不是真删除）进行一轮向下调整，恢复堆的结构。

代码如下：

Swap(&arr[0], &arr[end]);
AdjustDownSmall(arr, end, 0);
--end;

动图演示：

3.3 重复上述过程

重复上述交换与调整的过程，直到堆的大小为1，排序完成。

4.复杂度分析

时间复杂度：向下调整建堆的时间复杂度为O(N)，向下调整的时间复杂度为O(logN)，一共N次。因此总时间为O(N+NlogN)，时间复杂度为O(NlogN)。

空间复杂度：由于没有开辟额外的空间，因此空间复杂度为O(1)。

5.完整代码

5.1算法实现代码

#include<stdio.h>

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

// 建小堆
void AdjustDownSmall(int* arr, int n, int parent)
{
	// 假设左孩子小
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 如果右孩子存在且比左孩子小，则选择右孩子进行比较
		if (child + 1 < n && arr[child + 1] < arr[child])
		{
			++child;
		}
		// 如果选中的孩子节点小于父节点，则交换它们，并继续向下调整  
		if (arr[child] < arr[parent])
		{
			Swap(&arr[child], &arr[parent]); // 交换父节点和孩子节点  
			parent = child;			// 更新父节点为原来的孩子节点  
			child = parent * 2 + 1; // 更新child为新的父节点的左孩子索引  
		}
		else
		{
			// 如果孩子节点不小于父节点，则无需继续调整，跳出循环
			break;
		}
	}
}

// 建大堆
void AdjustDownLarge(int* arr, int n, int parent)
{
	int child = parent * 2 + 1;
	while (child < n)
	{
		// 如果右孩子存在且比左孩子大，则选择右孩子进行比较  
		if (child + 1 < n && arr[child + 1] > arr[child])
		{
			++child; // 更新child为右孩子的索引  
		}
		// 如果选中的孩子节点大于父节点，则交换它们，并继续向下调整  
		if (arr[child] > arr[parent])
		{
			Swap(&arr[child], &arr[parent]); // 交换父节点和孩子节点  
			parent = child;			// 更新父节点为原来的孩子节点  
			child = parent * 2 + 1; // 更新child为新的父节点的左孩子索引  
		}
		else
		{
			// 如果孩子节点不大于父节点，则无需继续调整，跳出循环  
			break;
		}
	}
}

void HeapSort_Down(int* arr, int n)
{
	// 向下调整建堆 
	// 下标为i的节点的父节点下标：（i-1）/2
	// i=n - 1
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDownSmall(arr, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDownSmall(arr, end, 0);
		--end;
	}
}

void HeapSort_Up(int* arr, int n)
{
	// 向下调整建堆 
	// 下标为i的节点的父节点下标：（i-1）/2
	// i=n - 1
	for (int i = (n - 1 - 1) / 2; i >= 0; i--)
	{
		AdjustDownLarge(arr, n, i);
	}
	int end = n - 1;
	while (end > 0)
	{
		Swap(&arr[0], &arr[end]);
		AdjustDownLarge(arr, end, 0);
		--end;
	}
}

5.2 示例

在这里，我们使用一个简单的示例来测试一下堆排序。

代码如下：

int main()
{
	int arr[] = { 3,1,4,5,9,2,6,6,4,2 };
	int n = sizeof(arr) / sizeof(arr[0]);
	HeapSort_Down(arr, n);
	printf("降序排序：");
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	printf("\n");
	HeapSort_Up(arr, n);
	printf("升序排序：");
	for (int i = 0; i < n; i++)
	{
		printf("%d ", arr[i]);
	}
	return 0;
}

输出结果：

6.堆排序的优势

大数据集排序：在处理包含数百万或数十亿条记录的大型数据集时，堆排序的高效性使其成为首选算法之一。它能够快速地将数据排序，为后续的数据分析、挖掘或可视化工作提供有力支持。

实时系统：在需要快速响应的实时系统中，如实时数据分析、在线交易处理等，堆排序的快速排序能力能够确保系统的高效运行，减少用户等待时间。

优先级队列：堆排序的核心——堆数据结构，本身就是实现优先级队列的理想选择。优先级队列在任务调度、网络路由选择、页面置换算法等多个领域都有广泛应用。通过堆排序，可以高效地维护优先级队列的顺序，确保高优先级任务得到优先处理。

结束语

呀呼，简要的介绍了一下堆排序这一排序方法。

求点赞收藏评论关注！！！

感谢各位大佬！！！