Python八大排序（八）——堆排序

内容导读

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

内容图文

堆排序涉及到的概念

堆排序是利用 堆进行排序的
堆是一种完全二叉树
堆有两种类型: 大根堆 小根堆

两种类型的概念如下：
大根堆：每个结点的值都大于或等于左右孩子结点
小根堆：每个结点的值都小于或等于左右孩子结点
因为比较抽象，所以专门花了两个图表示

那么，什么是完全二叉树呢？
完全二叉树 是 一种除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐的树，向左对齐指的是：

像这样的树就不是完全二叉树：

如果给上面的大小根堆的根节点从1开始编号，则满足下面关系(下图就满足这个关系)：

如果把这些数字放入数组中，则如下图所示：其中，上面的数字是数组下标值，第一个元素占位用。

堆排序算法详解+Python实现

了解了堆。下面我们来看下堆排序的思想是怎样的(以大根堆为例)：

首先将待排序的数组构造出一个大根堆
取出这个大根堆的堆顶节点(最大值)，与堆的最下最右的元素进行交换，然后把剩下的元素再构造出一个大根堆
重复第二步，直到这个大根堆的长度为1，此时完成排序。

代码如下：

#8.堆排序

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1  # left = 2*i + 1
    r = 2 * i + 2  # right = 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)

    # Build a 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)


arr = [12, 11, 13, 5, 6, 7]
heapSort(arr)
n = len(arr)
for i in range(n):
    print(arr[i])

执行结果：

内容总结

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

内容备注

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

内容手机端

---