跳到主要内容

堆排序

介绍

堆排序(Heap Sort)是一种基于二叉堆数据结构的比较排序算法。它通过将待排序的数组构建成一个最大堆(或最小堆),然后逐步将堆顶元素(最大值或最小值)与堆的最后一个元素交换,并调整堆,最终得到一个有序的数组。堆排序的时间复杂度为 O(n log n),是一种高效的排序算法。

堆排序的核心思想是利用堆的性质:堆是一个完全二叉树,且每个节点的值都大于或等于(最大堆)或小于或等于(最小堆)其子节点的值。

堆排序的步骤

堆排序的过程可以分为以下几个步骤:

  1. 构建最大堆:将待排序的数组构建成一个最大堆。
  2. 交换堆顶元素:将堆顶元素(最大值)与堆的最后一个元素交换。
  3. 调整堆:将剩余的元素重新调整为最大堆。
  4. 重复步骤2和3:直到堆中只剩下一个元素,排序完成。

代码示例

以下是一个用 Python 实现的堆排序算法:

python
def heapify(arr, n, i):
largest = i # 初始化最大值为根节点
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点

# 如果左子节点存在且大于根节点
if left < n and arr[left] > arr[largest]:
largest = left

# 如果右子节点存在且大于当前最大值
if right < n and arr[right] > arr[largest]:
largest = right

# 如果最大值不是根节点
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[i], arr[0] = arr[0], arr[i] # 交换堆顶元素和最后一个元素
heapify(arr, i, 0) # 调整堆

# 示例
arr = [12, 11, 13, 5, 6, 7]
heap_sort(arr)
print("排序后的数组:", arr)

输入: [12, 11, 13, 5, 6, 7]
输出: 排序后的数组: [5, 6, 7, 11, 12, 13]

逐步讲解

1. 构建最大堆

首先,我们需要将数组构建成一个最大堆。最大堆的性质是每个父节点的值都大于或等于其子节点的值。我们可以从最后一个非叶子节点开始,逐步向上调整堆。

在上面的二叉树中,节点 12 是根节点,1113 是其子节点。我们需要从节点 11 开始调整堆。

2. 交换堆顶元素

在构建好最大堆后,堆顶元素是数组中的最大值。我们将堆顶元素与数组的最后一个元素交换,然后将剩余的元素重新调整为最大堆。

3. 调整堆

交换后,堆顶元素可能不再满足最大堆的性质,因此我们需要对堆进行调整,使其重新成为最大堆。

4. 重复步骤2和3

重复上述步骤,直到堆中只剩下一个元素,此时数组已经有序。

实际应用场景

堆排序在实际中有广泛的应用,尤其是在需要高效排序的场景中。例如:

  • 优先队列:堆排序可以用于实现优先队列,其中元素的优先级决定了它们的出队顺序。
  • 实时系统:在实时系统中,堆排序可以用于快速处理需要按优先级排序的任务。
  • 大数据处理:在处理大规模数据时,堆排序可以有效地减少排序时间。

总结

堆排序是一种高效的排序算法,其时间复杂度为 O(n log n)。它通过构建最大堆并逐步提取堆顶元素来实现排序。堆排序在实际中有广泛的应用,尤其是在需要高效排序的场景中。

附加资源与练习

  • 练习:尝试用堆排序对一个包含 10 个元素的数组进行排序,并观察每一步的变化。
  • 进一步学习:了解其他基于堆的数据结构,如优先队列和斐波那契堆。
提示

堆排序虽然高效,但在实际应用中,由于其空间复杂度较高,通常用于需要稳定排序的场景。