Python算法——堆排序

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它通过将元素构建成一个最大堆或最小堆，然后重复从堆中移除根节点，直到堆为空，从而得到有序数组。堆排序是一种原地排序算法，具有稳定的时间复杂度，通常效率较高。本文将详细介绍堆排序的工作原理和Python实现。

堆排序的工作原理

堆排序的基本思想是：

1. 构建一个最大堆或最小堆，将数组元素视为二叉树的节点。
2. 交换堆的根节点（最大值或最小值）和堆的最后一个节点。
3. 从堆中移除最后一个节点，然后维护堆的性质。
   4, 重复步骤 2 和 3，直到堆为空。
   堆可以被看作是一个二叉树，其中每个节点的值都大于或小于其子节点的值，根据堆的性质，我们可以得到最大堆和最小堆两种堆的排序方式。最大堆要求父节点的值大于等于子节点的值，最小堆要求父节点的值小于等于子节点的值。

下面是一个示例，演示堆排序的过程：

原始数组：[9, 6, 5, 2, 8]

1. 构建最大堆，得到 [9, 8, 5, 2, 6]。
2. 交换根节点 9 和最后一个节点 6，得到 [6, 8, 5, 2, 9]。
3. 从堆中移除节点 9，然后维护堆的性质，得到 [8, 6, 5, 2]。
   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 是待排序的数组。
• heapify 函数用于将节点 i 下沉，以维护最大堆的性质。
• heap_sort 函数用于构建最大堆和执行堆排序。

示例代码

下面是一个使用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 = [9, 6, 5, 2, 8]
heap_sort(arr)
print("排序后的数组:", arr)

时间复杂度

堆排序的时间复杂度为 O(n log n)，其中 n 是数组的长度。它是一种原地排序算法，不需要额外的空间，因此非常适合排序大型数据集。

总之，堆排序是一种高效的排序算法，通过构建最大堆并重复移除根节点，实现了对数组的排序。了解堆排序有助于理解堆数据结构和排序算法的结合使用，提供了一种高效的排序解决方案。