python实现大顶堆调整 堆排序

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python实现大顶堆调整 堆排序，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含2477字，纯文字阅读大概需要4分钟。

内容图文

origin = [31, 72, 83, 42, 59, 13, 61, 25, 92]
origin = [0] + origin  # 后面用索引 方便对应规则
count_point = len(origin) - 1
def print_tree(array,unit_width=2): #打印出二叉树的样子，方便观察
    '''
    depth = 4 （深度） 每层满个数（2的（层数-1）次方）  打印出儿叉树的样子 每层前后补空格 空格规律前空格 7310 间隔空格0731
    1 3  7     0
    2 2  3     7
    3 1  1     3
    4 0  0     1
    :param array:
    :param unit_width:
    :return:
    '''
    length = len(array)
    depth = len(bin(length))-2
    index = 1
    space = ' '*unit_width
    for i in range(depth-1,-1,-1):
        pre = 2 ** i - 1#前空格数目
        print(pre * space,end='')
        offset = 2 ** (depth -i -1)#每层起点索引
        line = array[index:index+offset] #每层开始至结束
        lafter = space*(2*pre+1)#后空格数目
        print(lafter.join(map(str,line)))
        #print(line)
        index += offset
print_tree(origin)
print(count_point)
def heap_adjust(array,i,count_point): #堆调整左右先假设一个是两个之中最大的(目的不交换两个的位置取出索引) 然后比较一下 得到最大的数的索引
    while 2 * i <= count_point:
        lchild_index = 2 * i
        max_child_index = lchild_index
        if count_point > lchild_index and array[lchild_index] < array[lchild_index+1]:
            max_child_index = lchild_index + 1
        if array[max_child_index] > array[i]: #如果此父节点比他儿子节点的一个值要小  两节点交换位置
            array[i], array[max_child_index] = array[max_child_index], array[i]
            i = max_child_index #值换了 对应索引再换回来 相当于为上一层准备了 下面的假设最大数的索引
        else:
            break
def max_heap(array:list):
    for i in range(count_point//2,0,-1):# 找到最后一个有叶子节点的堆
        heap_adjust(array,i,count_point)#其实就是 heap_adjust的反复循环 直到每个父节点 都比子节点数值大
    return  array
# print_tree(max_heap(origin)) #调整并不能排序 无叶子节点的 兄弟节点之间的顺序
# print(origin)
def sort(array:list,count_point):
    while count_point > 1: #当节点数 大于一 对照count_point -=1 来看 循环的过程中节点数在减小 为什么 往下看
        array[1], array[count_point] = array[count_point], array[1] #不断将最后一个节点放到（根节点的位置上），由于根结点经过大顶堆 调整后每次都会是最大的那个这样每次取出就是排序
        count_point -= 1 #任何排序都有有序区和无序区  无序区的减有序区的增  节点数减一即根节点放入了列表尾部索引对应即有序区慢慢增大
        if count_point == 2 and array[2] >= array[1]:# 最后两个数不需要再进入堆调整  直接比较一下 排个序
            break
        heap_adjust(array,1,count_point)
    return array
max_heap(origin)#1.调出大顶堆
print_tree(origin)
sort(origin,count_point)#2.排序
print_tree(origin)
print(origin)#3.结果

---

<iframe border="0" height="86" src="//music.163.com/outchain/player?type=2&id=482894&auto=1&height=66" width="330"></iframe>

---

内容总结

以上是互联网集市为您收集整理的python实现大顶堆调整 堆排序全部内容，希望文章能够帮你解决python实现大顶堆调整 堆排序所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---