龙空技术网

用Python写一个堆排序代码含注释说明。

幻化意识流 174

前言:

现在兄弟们对“heappython”大体比较看重,姐妹们都需要了解一些“heappython”的相关资讯。那么小编在网摘上搜集了一些对于“heappython””的相关文章,希望朋友们能喜欢,看官们快快来学习一下吧!

大家好!我是幻化意识流。

今天我们用Python写一个堆排序的代码,文章的最后部分我做了注释说明,欢迎大家一起学习:

# 定义堆排序函数

def heap_sort(arr):

# 从最后一个非叶子节点开始构造初始堆

for i in range(len(arr) // 2 - 1, -1, -1):

heapify(arr, len(arr), i)

# 依次将堆顶元素和最后一个元素交换,并对前面的元素重新构造堆

for i in range(len(arr) - 1, 0, -1):

arr[0], arr[i] = arr[i], arr[0]

heapify(arr, i, 0)

# 定义堆化函数

def heapify(arr, n, i):

largest = i # 初始化最大值为父节点

l = 2 * i + 1 # 左子节点

r = 2 * i + 2 # 右子节点

# 找出最大值所在的节点

if l < n and arr[l] > arr[largest]:

largest = l

if r < n and arr[r] > arr[largest]:

largest = r

# 如果最大值不是父节点,则交换父节点和最大值所在节点的值,并递归地堆化下去

if largest != i:

arr[i], arr[largest] = arr[largest], arr[i]

heapify(arr, n, largest)

下面我来写一个代码说明:

定义heap_sort函数,参数为待排序的列表arr。从最后一个非叶子节点开始,逐个构造初始堆,即调用heapify函数。依次将堆顶元素和最后一个元素交换,并对前面的元素重新构造堆,即循环调用heapify函数。定义heapify函数,参数为待堆化的列表arr、列表长度n和父节点的索引i。初始化最大值为父节点的索引。找出左右子节点中最大值所在的节点。如果最大值不是父节点,则交换父节点和最大值所在节点的值,并递归地堆化下去,即调用heapify函数。

标签: #heappython