- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
CFSDN坚持开源创造价值,我们致力于搭建一个资源共享平台,让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章浅析经典排序算法之堆排序由作者收集整理,如果你对这篇文章有兴趣,记得点赞哟.
堆通常是一个可以被看做一棵树(完全)的数组对象。且总是满足以下规则:
堆是一棵完全二叉树 。
节点总是大于(或小于)它的孩子节点.
因此,根据第二个特性,就把二叉堆分为大顶堆(或叫最大堆),和小顶堆(或叫最小堆).
在上图中,1 2 是大顶堆 ,3 4 是小顶堆。判断是不是堆的条件:「从根结点到任意结点路径上结点序列的有序性!大顶堆和小顶堆判断序列是顺序还是逆序!」 。
Python并没有提供“堆”这种数据类型,它是直接把列表当成堆处理的。Python提供的heapq包中有一些函数,提供执行堆操作的工具函数 。
>>> import heapq 。
>>> heapq.__all__ 。
['heappush', 'heappop', 'heapify', 'heapreplace', 'merge', 'nlargest', 'nsmallest', 'heappushpop'] 。
堆排序 。
往堆中插入一个元素后,我们就需要进行调整,让其重新满足堆的特性,这个过程叫做堆化(heapify).
那么堆排序的基本思路是怎么样的呢?
下面举个例子(资源来自王争算法),比如在上面的大顶堆中添加数据22.
堆化非常简单,就是顺着节点所在的路径,向上或者向下,对比,然后交换.
堆排序的删除操作,这里一般指的是堆顶元素,当我们删除堆顶元素之后,就需要把第二大的元素放到堆顶,那第二大元素肯定会出现在左右子节点中.
然后我们再迭代地删除第二大节点,以此类推,直到叶子节点被删除。但是这样会产生一个数组空洞的问题.
因此,这里面又个技巧,就是删除堆顶元素的时候,不能直接删除,要用堆顶元素和最后一个元素做交换,然后根据堆的特点调整堆,直到满足条件.
排序的过程就是每次待排序的序列长度减去1再执行这两步.
下面给出通过Python中的heapq模块实现的堆排序简单代码.
from heapq import heappop, heappush 。
。
def heap_sort(array): 。
heap = [] 。
for element in array: 。
heappush(heap, element) 。
。
ordered = [] 。
。
while heap: 。
ordered.append(heappop(heap)) 。
return ordered 。
。
array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2] 。
print(heap_sort(array)) 。
# [2, 4, 5, 13, 15, 17, 18, 21, 24, 26] 。
如果不使用heapq模块,对于推排序需要了解堆排序中的建堆过程.
将数组原地建成一个堆。不借助另一个数组,就在原数组上操作。建堆的过程,有两种思路.
第一种建堆思路的处理过程是从前往后处理数组数据,并且每个数据插入堆中时,都是从下往上堆化。而第二种实现思路,是从后往前处理数组,并且每个数据都是从上往下堆化.
也就是如果节点的下标是 i,那左子节点的下标就是 2∗i+1,右子节点的下标就是 2∗i+2,父节点的下标就是 .
def heap_sort(array): 。
n = len(array) 。
# 从尾部开始建堆,这样保证子节点有序 。
for i in range((n-1)//2, -1, -1): 。
_shift(array, n, i) 。
# 依次把堆顶元素交换到最后,重建堆顶(堆不包含刚交换的最大元素) 。
for i in range(n-1, 0, -1): 。
array[0], array[i] = array[i], array[0] 。
_shift(array, i, 0) 。
return array 。
。
# 重建堆顶元素 n:堆元素个数,i:堆建顶位置 。
def _shift(array, n, i): 。
# 如果没有子节点,直接返回 。
if i*2+1 >= n: 。
return 。
# 取最大子节点位置 。
maxsub = i*2+2 if i*2+2 < n and array[i*2+1] <= array[i*2+2] else i*2+1 。
# 如果节点小于最大子节点,交换元素,递归以子节点为堆顶重建 。
if array[i] < array[maxsub]: 。
array[i], array[maxsub] = array[maxsub], array[i] 。
_shift(array, n, maxsub) 。
。
if __name__ == '__main__': 。
array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2] 。
print(heap_sort(array)) 。
。
# [2, 4, 5, 13, 15, 17, 18, 21, 24, 26] 。
堆排序不是稳定的排序算法,因为在排序的过程,存在将堆的最后一个节点跟堆顶节点互换的操作,所以就有可能改变值相同数据的原始相对顺序。堆排序整体的时间复杂度是O(nlogn) .
参考资料 https://github.com/MaoliRUNsen/runsenlearnpy100 。
原文地址:https://mp.weixin.qq.com/s/1iRQ0OtG0SCEOSBPCOVSig 。
最后此篇关于浅析经典排序算法之堆排序的文章就讲到这里了,如果你想了解更多关于浅析经典排序算法之堆排序的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。
很多朋友或许都有这个疑问,一个网站域名和网站的排名有关系吗?今天本文就从三个方面分析网站的域名与网站的排名有没有关系,希望对大家有一定的帮助。 1、全拼双拼域名 首先,我们要知道在这一点百
什么是进程 当一个程序进入内存中运行起来它就变为一个进程。因此,进程就是一个处于运行状态的程序。同时进程具有独立功能,进程是操作系统进行资源分配和调度的独立单位。 什么是线程 线程是进
最近几年,互联网络竞争异常激烈,各个企业为了增加业绩,都在网络销售中下足了功夫。要确定网站发展的方向,必须给自己的网站制定好一个发展目标,有了目标才能更好的发展。不管
一.基础知识准备: 1.层的原则: (1)每一层以接口方式供上层调用。 (2)上层只能调用下层。 (3)依赖分为松散交互和严格交互两种。 2.业务逻辑分类: (1)应
编程时一门技术,更是一门艺术 简单工厂模式利用面向对象方式通过继承、封装、多态把程序的耦合度降低,设计模式使得程序更加灵活,容易修改,易于复用。 下面是服务器计算器代码:
对于策略模式的理解:当一个业务有多种需求时候,在某个时候需要使用不同的方式来计算结果。这时候不同的方式可以理解为不同的策略来解决同样的问题。 例如:商场收银系统计算价格,1:正常计算 2:商品打折计
随着 Kubernetes 在企业中应用的越来越广泛和普及,越来越多的公司在生产环境中运维多个集群。本文主要讲述一些关于多集群 Kubernetes 的思考,包括为什么选择多集群,多集群的好处以
Kubelet 出于对节点的保护,允许在节点资源不足的情况下,开启对节点上 Pod 进行驱逐的功能。最近对 Kubelet 的驱逐机制有所研究,发现其中有很多值得学习的地方,总结下来
以下分析不针对任何快递公司,纯属实说。 申通快递在快递行业中速度与费用都属于中等的水平,在国内也分布有很多投递点,一般地区都可以投递到;顺丰在国内是速度最快的快递公司之一,一般来说隔天就能够到,其
概述 流(streams)是PHP4.3版本引入的一个特性,主要是为了统一文件、sockets以及其他类似资源的工作方法。PHP4.3距今已经有很长时间了,但是很多程序员似乎都不能正确使用PHP中
Pre 很早在看 Jesse 的 Asp.net Core快速入门 的课程的时候就了解到了在Asp .net core中,如果添加的Json配置被更改了,是支持自动重载配置的,作为一名有着严重&q
之前对closure一知半解,在网上也找不到一篇文章能把它说清楚,今天好像第一次对它有点清晰的了解 了,写个BLOG记念一下 lua的函数是一种 First-Class Value 的东西, 到底
1、什么是默认方法,为什么要有默认方法 简单说,就是接口可以有实现方法,而且不需要实现类去实现其方法。只需在方法名前面加个default关键字即可。 为什么要有这个特性?首先,之前的接口是个双
信息数据传输的安全一直都是个很重要的话题,从刚开始当程序员时错以为MD5、SHA1这些哈希算法就是加密算法,到后来慢慢接触对称加密、非对称加密这些概念,再到对接各种大开发平台接口的时候看到他们通
前言 2021年,vanilla-extract 作为黑马登顶了 css-in-js 满意度榜首(虽然使用率仅为1%),号称是一个类型安全、高度兼容 TS 场景的库,国内相关讨论还很少,稍微看
(一)响应式数据 1. 简单例子 从最简单的数据绑定开始,在 Vue 2.0 中,我们这样将一个数据绑定到模板的指定位置: 在组件创建参数的 data 构造函数中返回一个用来绑定的数据对象,其
我是一名优秀的程序员,十分优秀!