Python中的堆排序是什么？

堆排序是基于二叉堆数据结构的排序技术。要进行堆排序，您需要熟悉二叉树和二叉堆。

更多Python相关文章，请阅读：Python 教程

什么是完全二叉树？

完全二叉树是一种树形数据结构，除最后一层外的所有级别都被完全填充。最后一层必须从左侧填充。

什么是二叉堆？

二叉堆是二叉树的特殊情况。二叉堆有两种类型-

最大堆-每个级别的父节点都大于其子节点。
最小堆-每个级别的父节点都小于其子节点。

完全二叉树的数组表示

二叉堆可以表示为数组，因为它具有空间效率。如果将父节点存储在索引I处，左侧子节点可以通过2 * i + 1计算，右侧子节点可以通过2 * i + 2计算。假设索引从0开始。

堆排序算法

从完全二叉树构建最大堆。
删除根并将其替换为堆中的最后一个元素，减小堆的大小1并从剩余节点再次构建最大堆。
重复步骤2，直到只剩下1个节点。

从完全二叉树中构建最大堆

这是从完全二叉树构建最大堆的代码，其中将两个子节点与根比较。如果较大的元素不是根，则将较大的元素与根交换。这是一个递归过程。当前的根比其子节点小，将连续比较到其正确位置。

以下代码从完全二叉树（基本上是我们要排序的数组）构建最大堆。

def heapify(arr, n, i):
   # 在根和子节点中找到最大的元素
   largest = i
   l = 2 * i + 1
   r = 2 * i + 2
   if l < n and arr[i] < arr[l]:
      largest = l
   if r < n and arr[largest] < arr[r]:
      largest = r
   # 如果根不是最大的，则与最大的交换并继续堆排
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

堆排序

此时，我们拥有最大堆。现在我们需要做以下事情。

将根与堆中的最后一个元素交换。
减少堆的大小1。（这意味着最大的元素已经到达最后一个位置，我们不需要考虑该元素）。
重建不包括最后一个元素的最大堆。
重复上述步骤，直到只剩下1个元素。

for i in range(n-1, 0, -1): # 交换 
    arr[i], arr[0] = arr[0], arr[i] # 对根元素进行堆排 
    heapify(arr, i, 0)

完整的Python堆排序程序如下所示 −

def heapify(arr, n, i):
   # 找出根节点和子节点中最大的一个
   largest = i
   l = 2 * i + 1
   r = 2 * i + 2
   if l < n and arr[i] < arr[l]:
      largest = l
   if r < n and arr[largest] < arr[r]:
      largest = r
   # 如果根节点不是最大的，就和最大的交换并继续构造堆结构
   if largest != i:
      arr[i], arr[largest] = arr[largest], arr[i]
      heapify(arr, n, largest)

def heapSort(arr):
   n = len(arr)
   # 构造最大堆
   for i in range(n//2, -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 = [1, 12, 9, 5, 6, 10]
heapSort(arr)
n = len(arr)
print("排序后的数组")
for i in range(n):
   print(arr[i], end=' ')

时间复杂度 – O(n logn)