Python堆排序
本教程将展示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] [largest_index] [parent_index] [largest_index] [largest_index] [parent_index] 现在，我们有了一个函数，它取我们数组内的最大值，并把它放在我们堆的根部。我们需要一个函数来获取未排序的数组，调用build_heap() 函数并从堆中提取元素。
下面的代码片断演示了Python中heapSort() 函数的实现。
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 。
这意味着我们从最后一个父节点开始，逐步减少我们的索引，直到我们到达根节点。
第二个循环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]
正如我们所看到的，我们的数组已经完全排序了。这意味着我们的代码运行良好。
如果我们想按降序排序，我们可以创建一个最小堆而不是上面实现的最大堆。
本文不会解释min-heap，因为在本教程的开头已经讨论了什么是min-heap。
我们的程序以如下方式工作。下面的块显示了我们的数组在代码执行的每个阶段的状态。
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() 函数。这个过程对length - 1 ，我们的数组被排序了。
