面试必备算法|图解堆排序(Python)

简介: Python堆排序图解。

堆排序

堆排序的思想

​ 堆排序是用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

​ 以大顶堆为例,现将列表构造成一个大顶堆,此时,整个列表的最大值就是堆顶的值。将其与末尾元素进行交换,此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆,这样会得到n个元素的次小值。如此反复执行,便能得到一个有序列表了。具体可以总结为下面的三个步骤:

  • 将无序列表构建成一个堆,根据升序降序需求选择大顶堆或小顶堆;
  • 将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;
  • 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个列表有序。

图解堆排序

​ 在了解堆排序之前我们需要先了解堆的概念。对于堆结构我们可以分为大顶堆和小顶堆两种:

  • 大顶堆:每个节点的值都大于或等于其子节点的值,在堆排序算法中用于升序排列;
  • 小顶堆:每个节点的值都小于或等于其子节点的值,在堆排序算法中用于降序排列;

​ 大顶堆和小顶堆的结构如下所示:

在这里插入图片描述

​ 了解了大顶堆和小顶堆的含义之后,我们开始了解堆排序的过程,首先给出如下的一个无序列表,我们用堆的形式来表示这个列表。

  • 第一步:将无序列表构建成一个大顶堆

在这里插入图片描述

​ 对于这个堆我们的目的是构造出一个大顶堆,构造的过程中我们需要不断的比较每一个堆结构的大小关系,并切把大的元素调整为父节点,对于325三个元素组成的子堆举例:
在这里插入图片描述

​ 经过上述子堆的调整后,原堆的结构如下:

在这里插入图片描述

​ 继续用上述方法调整154三个元素组成的子堆:

在这里插入图片描述

​ 经过本次调整之后,我们发现整个堆的堆顶(5)已经是最大的了,但是调整之后的子堆123又变的混乱了,此时我们再一次对该子堆做调整:

在这里插入图片描述

​ 至此我们把最开始的无序列表构造成了一个大顶堆,接下来就要进行排序的操作了。

  • 第二步:将堆顶元素与末尾元素交换,将最大元素"沉"到数组末端;

​ 首先我们将堆顶元素5和末尾元素1做交换:

在这里插入图片描述

​ 进行完本次操作我们可以发现最大的元素5就被放倒了最后的位置,此时我们把5先抛除。

  • 第三步:重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素,反复执行调整+交换步骤,直到整个列表有序。

​ 对于剩下的列表[1342]继续按照第一步的方法构造出大顶堆,然后按照第二步的方法继续找到最大的元素即可,直到排序完成:
在这里插入图片描述
堆排序的性质

最优时间复杂度:O(nlog2n)
最坏时间复杂度:O(nlog2n)
稳定性:不稳定

堆排序的代码实现

lst = list(map(int, input().split(',')))


# 创建堆(调整堆)
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)
    return arr


heapSort(lst)
AI 代码解读
目录
打赏
0
0
0
0
16
分享
相关文章
解锁文件共享软件背后基于 Python 的二叉搜索树算法密码
文件共享软件在数字化时代扮演着连接全球用户、促进知识与数据交流的重要角色。二叉搜索树作为一种高效的数据结构,通过有序存储和快速检索文件,极大提升了文件共享平台的性能。它依据文件名或时间戳等关键属性排序,支持高效插入、删除和查找操作,显著优化用户体验。本文还展示了用Python实现的简单二叉搜索树代码,帮助理解其工作原理,并展望了该算法在分布式计算和机器学习领域的未来应用前景。
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
32 12
基于 Python 的布隆过滤器算法在内网行为管理中的应用探究
在复杂多变的网络环境中,内网行为管理至关重要。本文介绍布隆过滤器(Bloom Filter),一种高效的空间节省型概率数据结构,用于判断元素是否存在于集合中。通过多个哈希函数映射到位数组,实现快速访问控制。Python代码示例展示了如何构建和使用布隆过滤器,有效提升企业内网安全性和资源管理效率。
36 9
|
12天前
|
内网桌面监控软件深度解析:基于 Python 实现的 K-Means 算法研究
内网桌面监控软件通过实时监测员工操作,保障企业信息安全并提升效率。本文深入探讨K-Means聚类算法在该软件中的应用,解析其原理与实现。K-Means通过迭代更新簇中心,将数据划分为K个簇类,适用于行为分析、异常检测、资源优化及安全威胁识别等场景。文中提供了Python代码示例,展示如何实现K-Means算法,并模拟内网监控数据进行聚类分析。
32 10
解锁文档管理系统高效检索奥秘:Python 哈希表算法探究
在数字化时代,文档管理系统犹如知识宝库,支撑各行各业高效运转。哈希表作为核心数据结构,通过哈希函数将数据映射为固定长度的哈希值,实现快速查找与定位。本文聚焦哈希表在文档管理中的应用,以Python代码示例展示其高效检索特性,并探讨哈希冲突解决策略,助力构建智能化文档管理系统。
探究办公室电脑怎么共享文件的 Python 算法
在数字化办公环境中,高效文件共享是提升工作效率的关键。本文聚焦于使用Python实现办公室电脑文件共享的算法,涵盖需求分析、基础实现及优化拓展。通过socket编程和文件流操作,实现文件传输,并探讨多线程、权限管理和文件索引等优化措施,确保文件共享的安全性和便捷性,助力现代办公协同。
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
本文介绍了多线程环境下的几个关键概念,包括时间片、超线程、上下文切换及其影响因素,以及线程调度的两种方式——抢占式调度和协同式调度。文章还讨论了减少上下文切换次数以提高多线程程序效率的方法,如无锁并发编程、使用CAS算法等,并提出了合理的线程数量配置策略,以平衡CPU利用率和线程切换开销。
面试官:单核 CPU 支持 Java 多线程吗?为什么?被问懵了!
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
本文详解自旋锁的概念、优缺点、使用场景及Java实现。关注【mikechen的互联网架构】,10年+BAT架构经验倾囊相授。
大厂面试高频:什么是自旋锁?Java 实现自旋锁的原理?
大厂面试必看!Java基本数据类型和包装类的那些坑
本文介绍了Java中的基本数据类型和包装类,包括整数类型、浮点数类型、字符类型和布尔类型。详细讲解了每种类型的特性和应用场景,并探讨了包装类的引入原因、装箱与拆箱机制以及缓存机制。最后总结了面试中常见的相关考点,帮助读者更好地理解和应对面试中的问题。
106 4

热门文章

最新文章

AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等