Python中的堆排序是什么？
堆排序是一种基于二叉堆数据结构的排序技术。为了进行堆排序，您需要熟悉二叉树和二叉堆。
什么是完全二叉树？
完全二叉树是一种树数据结构，其中除最后一层外的所有级别都被完全填充。最后一层必须从左侧填充。
什么是二叉堆？
二叉堆是二叉树的一个特例。二元堆有两种类型-
MaxHeap-每个级别的父节点大于其子节点。
MinHeap-每个级别的父节点都小于其子节点。
完全二叉树的数组表示
二叉堆可以表示为一个数组，因为它节省空间。如果父节点存储在索引I处，则左子节点可以通过2*i+1计算，右子节点可以通过2*i+2计算。假设索引从0开始。
堆排序算法
从完整的二叉树构建最大堆。
删除根并用堆中的最后一个元素替换它，将堆的大小减少1，然后再次从剩余节点构建最大堆。
重复步骤2，直到我们只剩下1个节点。
从完整的二叉树构建最大堆
这是从完全二叉树构建最大堆的代码，其中两个子节点与根进行比较。如果较大的元素不是根，则将较大的元素与根交换。这是一个递归过程。小于其子节点的当前根不断与其较低的子树进行比较，除非它到达其正确位置。
下面的代码从一个完整的二叉树构建一个最大堆，它基本上是我们想要排序的数组。
def heapify(arr, n, i):
#在root和children中找到最大的
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):
#在root和children中找到最大的
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("Sorted array is")
for i in range(n):
print(arr[i], end=' ')时间复杂度-O(nlogn)
热门推荐
10 八一幼儿祝福语大全简短
11 公司乔迁食堂祝福语简短
12 婚礼结束聚餐祝福语简短
13 儿媳买车妈妈祝福语简短
14 毕业送礼老师祝福语简短
15 同事辞职正常祝福语简短
16 恭贺新婚文案祝福语简短
17 金店立秋祝福语简短英文
18 婆婆高寿祝福语大全简短