迹忆客 专注技术分享

本篇文章将介绍堆排序算法在 Python 中的实现。

Python中的堆排序算法

堆排序是一种强大的算法，用于在 Python 中对数组和列表进行排序。 它很受欢迎，因为它非常快，并且不像合并排序和快速排序那样占用任何额外空间。

堆排序的时间复杂度是O(n*log(n))。

堆排序是一种就地算法，它不再创建任何数据结构来保存数据的中间状态。 相反，它对我们的原始数组进行了更改。

因此，当数据非常大时，这为我们节省了大量空间。

该算法唯一的缺点是它非常不稳定。 如果我们的数组中有多个元素在不同索引处具有相同的值，则它们的位置将在排序时发生变化。

堆排序算法的工作原理是递归地创建一个最小或最大堆，取出根节点，将其放在我们数组中的第一个未排序索引处，并将最后一个堆元素转换为根节点。

这个过程递归重复，直到我们在堆中留下一个节点。 最后，最后一个堆元素被放置在我们数组的最后一个索引处。

如果我们想一想，这个过程类似于选择排序算法，因为我们取最大值或最小值并将它们放在已排序数组的顶部。

在 Python 中实现堆排序算法

我们将首先了解实现 build_heap() 函数，该函数采用原始数组、数组的长度和父节点的索引。 在这里，如果我们查看一个数组，最后一个父节点的索引位于我们数组内的 (n//2 - 1) 处。

类似地，该特定父级的左孩子的索引为 2*parent_index + 1，右孩子的索引为 2*parent_index + 2。

在这个例子中，我们试图创建一个最大堆。 这意味着每个父节点都需要大于其子节点。

为此，我们将从最后一个父节点开始，向上移动到堆的根节点。 如果我们想创建一个最小堆，我们希望所有父节点都小于它们的子节点。

此 build_heap() 函数将检查左或右子节点是否大于当前父节点，并将最大节点与父节点交换。

该函数递归地调用自身，因为我们希望对堆中的所有父节点递增地重复之前的过程。

以下代码片段演示了上述 built_heap() 函数在 Python 中的有效实现。

def build_heap(arr, length, parent_index):
    largest_index = parent_index
    left_index = 2 * parent_index + 1
    right_index = 2 * parent_index + 2

    if left_index < length and arr[parent_index] < arr[left_index]:
        largest_index = left_index

    if right_index < length and arr[largest_index] < arr[right_index]:
        largest_index = right_index

    if largest_index != parent_index:
        arr[parent_index],arr[largest_index] = arr[largest_index],arr[parent_index]

        build_heap(arr, length, largest_index)

现在，我们有一个函数，它获取数组中的最大值并将其放在堆的根部。 我们需要一个函数来获取未排序的数组，调用 build_heap() 函数并从堆中提取元素。

以下代码片段演示了 heapSort() 函数在 Python 中的实现。

def heapSort(arr):
    length = len(arr)

    for parent_index in range(length // 2 - 1, -1, -1):
        build_heap(arr, length, parent_index)

    for element_index in range(length-1, 0, -1):
        arr[element_index], arr[0] = arr[0], arr[element_index]
        build_heap(arr, element_index, 0)

我们在数组中逐步调用每个父节点的 build_heap() 函数。 请注意，我们将 length//2-1 作为起始索引，-1 作为结束索引，步长为 -1。

这意味着我们从最后一个父节点开始，递减索引 1，直到到达根节点。

第二个 for 循环从我们的堆中提取元素。 它也从最后一个索引开始，并在我们数组的第一个索引处停止。

我们在此循环中交换数组的第一个和最后一个元素，并通过传递 0 作为根索引对新排序的数组执行 build_heap() 函数。

现在，我们已经编写了用 Python 实现堆排序的程序。 是时候对数组进行排序并测试上面编写的代码了。

arr = [5, 3, 4, 2, 1, 6]
heapSort(arr)
print("Sorted array :", arr)

输出:

Sorted array : [1, 2, 3, 4, 5, 6]

如我们所见，我们的数组已完全排序。 这意味着我们的代码工作得很好。

如果我们想按降序排序，我们可以创建一个最小堆而不是上面实现的最大堆。

本文不会解释最小堆，因为它已经在本教程的开头讨论了最小堆是什么。

我们的程序以下列方式工作。 以下块显示了我们的数组在代码执行的每个阶段的状态。

Original Array [5, 3, 4, 2, 1, 6] # input array
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 1
Building Heap [5, 3, 6, 2, 1, 4] # after build_heap() pass 2
Building Heap [6, 3, 5, 2, 1, 4] # after build_heap() pass 3
Extracting Elements [6, 3, 5, 2, 1, 4] # before swapping and build_heap pass 1
Extracting Elements [5, 3, 4, 2, 1, 6] # before swapping and build_heap pass 2
Extracting Elements [4, 3, 1, 2, 5, 6] # before swapping and build_heap pass 3
Extracting Elements [3, 2, 1, 4, 5, 6] # before swapping and build_heap pass 4
Extracting Elements [2, 1, 3, 4, 5, 6] # before swapping and build_heap pass 5
Sorted array : [1, 2, 3, 4, 5, 6] # after swapping and build_heap pass 5

build_heap() 函数执行了 3 次，因为我们的堆中只有 3 个父节点。

之后，我们的元素提取阶段获取第一个元素，将其与最后一个元素交换，然后再次执行 build_heap() 函数。 对长度 - 1 重复此过程，我们的数组得到排序。