堆排序的 Python 程序
pythonserver side programmingprogramming更新于 2024/1/23 0:13:00
在本文中，我们将了解下面给出的问题陈述的解决方案。
问题陈述− 给定一个数组，我们需要使用堆排序的概念对其进行排序。
在这里，我们将最大元素放在末尾。重复此操作，直到数组排序完成。
现在让我们观察下面实现中的解决方案−
示例
# heapify
def heapify(arr, n, i):
largest = i # 最大值
l = 2 * i + 1 # 左
r = 2 * i + 2 # 右
# 如果左孩子存在
如果 l < n 且 arr[i] < arr[l]:
largest = l
# 如果右孩子存在
if r < n and arr[largest] < arr[r]:
largest = r
# root
if largest != i:
arr[i],arr[largest] = arr[largest],arr[i] # swap
# root.
heapify(arr, n, largest)
# sort
def heapSort(arr):
n = len(arr)
# maxheap
for i in range(n, -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)
# main
arr = [2,5,3,8,6,5,4,7]
heapSort(arr)
n = len(arr)
print ("排序后的数组为")
for i in range(n):
print (arr[i],end=" ")
输出
排序后的数组为 2 3 4 5 5 6 7 8
所有变量均在局部范围内声明，其引用如上图所示。
结论
在本文中，我们了解了如何编写用于堆排序的 Python 程序
