[转载] python实现堆排序用类的方法_python实现堆排序的实例讲解

参考链接： 用Python进行堆排序heap sort

堆排序

堆是一种完全二叉树(是除了最后一层，其它每一层都被完全填充，保持所有节点都向左对齐)，首先需要知道概念：最大堆问题，最大堆就是根节点比子节点值都大，并且所有根节点都满足，那么称它为最大堆。反之最小堆。

当已有最大堆，如下图，首先将7提出，然后将堆中最后一个元素放到顶点上，此时这个堆不满足最大堆了，那么我们要给它构建成最大堆，需要找到此时堆中对打元素然后交换，此时最大值为6，符合最大堆后，我们将6提取出来，然后将堆中最后一个元素放到堆的顶部...以此类推。最后提取的数值7,6,5,4,3,2,1

那么在维护一个最大堆过程中，最多进行交换次数决定了此算法复杂度，但交换次数与树的高度有关：

​ h=log2(n+1)h=log2(n+1)

最大堆生成：根据最大堆特性(任意一个根节点都大于叶子节点)不满足就调换。

代码实现：

from collections import deque

def swap_param(L, i, j):

# 堆顶与最后元素交换

L[i], L[j] = L[j], L[i]

return L

def heap_adjust(L, start, end):

#构造成大根堆

temp = L[start]

i = start

j = 2 * i

while j <= end:

# 判断左右子节点，取两个子节点最大索引

if (j < end) and (L[j] < L[j + 1]):

j += 1

# 判断根节点与子节点比较，如果子节点大于根节点，子节点赋值给根节点

if temp < L[j]:

L[i] = L[j]

i = j

j = 2 * i

else:

break

# 再把 原来根节点值赋值给子节点上

L[i] = temp

def heap_sort(L):

L_length = len(L) - 1

first_sort_count = L_length // 2

for i in range(first_sort_count):

heap_adjust(L, first_sort_count - i, L_length)

for i in range(L_length - 1):

L = swap_param(L, 1, L_length - i)

heap_adjust(L, 1, L_length - i - 1)

return [L[i] for i in range(1, len(L))]

def main():

L = deque([50, 16, 30, 10, 60, 90, 2, 80, 70])

L.appendleft(0)

print(heap_sort(L))

main()

基础知识点扩展：

堆排序

堆

堆栈是计算机的两种最基本的数据结构。堆的特点就是FIFO(first in first out)先进先出，这里的话我觉得可以理解成树的结构。堆在接收数据的时候先接收的数据会被先弹出。

堆排序节点访问和操作定义

堆节点的访问

在这里我们借用wiki的定义来说明：

通常堆是通过一维数组来实现的。在阵列起始位置为0的情况中

父节点i的左子节点在位置(2*i+1);

父节点i的右子节点在位置(2*i+2);

子节点i的父节点在位置floor((i-1)/2);

到此这篇关于python实现堆排序的实例讲解的文章就介绍到这了,更多相关堆排序python实现内容请搜素我们以前的文章或下面相关文章，希望大家以后多多支持我们！

时间： -02-18

如果觉得《[转载] python实现堆排序用类的方法_python实现堆排序的实例讲解》对你有帮助，请点赞、收藏，并留下你的观点哦！