堆排序，学习笔记
目录
一、概念
堆排序是一种基于二叉堆数据结构的排序算法。二叉堆是一种完全二叉树，它分为两种类型：最大堆和最小堆。在最大堆中，每个节点的值都大于或等于它的子节点的值；在最小堆中，每个节点的值都小于或等于它的子节点的值。堆排序利用了堆的这种性质来实现排序
例如，对于一个最大堆，根节点的值是整个堆中的最大值。当我们要进行排序时，我们可以利用这个性质，每次将堆顶元素（最大值）取出，然后重新调整堆，使得剩余元素仍然保持堆的性质，如此反复，直到堆为空，就可以得到一个有序的序列
二、堆排序的基本思路
堆排序主要利用了堆的性质来实现排序。如果是要进行升序排序，就构建一个最大堆；如果是要进行降序排序，就构建一个最小堆。以升序排序为例，首先将待排序的数组构建成一个最大堆，此时堆顶元素（即数组的第一个元素）就是最大值。然后将堆顶元素与数组的最后一个元素交换位置，这样最大值就被放到了数组的最后。接着，对剩下的元素重新构建最大堆，再将堆顶元素与倒数第二个元素交换位置，如此反复，直到整个数组都有序
三、堆排序的基本步骤
1. 构建初始堆：
假设我们有一个数组arr，要将其构建成一个最大堆。首先，我们从最后一个非叶子节点开始调整堆。对于一个长度为n的数组，最后一个非叶子节点的索引是parent(n/2 - 1)，其中parent(i)表示节点i的父节点索引，计算公式为parent(i)=(i - 1)/2。
对于每个非叶子节点，我们比较它和它的子节点的值。如果它小于子节点的值，就将它和最大的子节点交换位置，然后继续向下调整，直到满足堆的性质。例如，对于节点i，它有左子节点2i + 1和右子节点2i+2（如果存在），我们比较arr[i]、arr[2i + 1]和arr[2i + 2]的值，将arr[i]与最大的子节点交换位置。
2. 排序过程
当构建好初始堆后，堆顶元素就是数组中的最大值。我们将堆顶元素arr[0]与数组的最后一个元素arr[n - 1]交换位置，此时最大值就被放到了数组的末尾。
然后，我们将剩下的n - 1个元素重新构建成一个堆，因为此时堆顶元素可能不满足堆的性质了。我们再次从根节点开始调整堆，使得剩余元素仍然是一个最大堆。
重复上述交换和调整堆的步骤，每次将当前堆中的最大值放到数组的已排序部分的末尾，直到整个数组都被排序。
四、示例
def heapify(arr, n, i):
largest = i
l = 2 * i + 1
r = 2 * i + 2
if l < n and arr[l] > arr[largest]:
largest = l
if r < n and arr[r] > arr[largest]:
largest = r
if largest!= i:
arr[i], arr[largest] = arr[largest], arr[i]
heapify(arr, n, largest)
def heap_sort(arr):
n = len(arr)
# 构建最大堆
for i in range(n // 2 - 1, -1, -1):
heapify(arr, n, i)
# 逐个提取元素进行排序
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
heapify(arr, i, 0)
return arr
arr = [12, 11, 13, 5, 6]
sorted_arr = heap_sort(arr)
print("排序后的数组:", sorted_arr)
在这个示例中，heapify函数用于调整堆，heap_sort函数用于实现整个堆排序的过程。首先通过heapify函数构建最大堆，然后通过交换堆顶元素和数组末尾元素，并重新调整堆的方式实现排序
五、应用场景
1. 优先级队列相关场景
任务调度系统：在多任务的系统中，不同的任务具有不同的优先级。例如，操作系统中的进程调度、后台服务中的任务管理等。可以使用堆来构建优先级队列，每次从堆中取出优先级最高的任务进行执行，确保高优先级的任务能够优先得到处理。比如，在一个视频编辑软件的后台，有多个视频渲染任务同时进行，高分辨率、紧急需求的视频渲染任务优先级更高，使用堆可以高效地管理这些任务的执行顺序
实时消息系统：在即时通讯、实时通知等应用中，消息的优先级可能不同。比如，重要的系统通知、用户的紧急消息等需要优先展示给用户。可以利用堆来管理消息队列，将高优先级的消息排在堆的顶部，以便及时处理和展示
2. TopK 值问题
在数据量较大的情况下，需要快速找到数据集中的前 K 个最大或最小的值。例如，在搜索引擎中，需要找出搜索频率最高的前 K 个关键词；在数据分析中，需要找出销售额排名前 K 的产品等。使用堆可以在不遍历整个数据集的情况下，快速地找到 TopK 值
原文地址：https://blog.csdn.net/jxnd123456/article/details/143677822
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！