python实现堆排序的实例讲解
作者:阿凯 发布时间:2023-01-06 20:50:38
标签:堆排序,python
堆排序
堆是一种完全二叉树(是除了最后一层,其它每一层都被完全填充,保持所有节点都向左对齐),首先需要知道概念:最大堆问题,最大堆就是根节点比子节点值都大,并且所有根节点都满足,那么称它为最大堆。反之最小堆。
当已有最大堆,如下图,首先将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);
来源:https://www.cnblogs.com/xujunkai/p/12340885.html
0
投稿
猜你喜欢
- 开发工具**Python版本:**3.6.4相关模块:pyecharts模块;以及一些Python自带的模块。环境搭建安装Python并添加
- 列表转化为字符串如下所示:>>> list1=['ak','uk',4]>>&
- 一、背景近期项目即将开展,计划第一步就是实现数据的可视化,所以先学习一下数据展示相关Demo。选用Python2.7与Matplotlib来
- 装饰器总结什么是装饰器?处理函数的函数,加一个功能,但是不影响原来函数的内部结构生活中的例子:给手机加一个外壳,外壳保护了手机装饰器有什么用
- server application error--IIS故障故障现象:Server Application Error The serve
- 下面是一份在 HTML 4 Strict 和 XHTML 1.0 Strict 下必须遵守的标签嵌套规则,比如你不能在 <a>
- python是支持多线程的,主要是通过thread和threading这两个模块来实现的。thread模块是比较底层的模块,threadin
- '*************************************************'函数名:getMaxO
- 尽管某些书籍上总是说避免使用全局变量,但是在实际的需求不断变化中,往往定义一个全局变量是最可靠的方法,但是又必须要避免变量名覆盖。Pytho
- 1.交换变量值2.将一列表中的所有元素拼接成字符串3.查找list中最高频率的值4.检查两个单词是否是字谜(组成的字母和对应数量一致)5.反
- 1、线程池模块引入from concurrent.futures import ThreadPoolExecutor2、使用线程池一个简单的
- 本文实例为大家分享了Python实现图形用户界面计算器的具体代码,供大家参考,具体内容如下简易用户图形界面计算器设计思路:简易图形用户界面计
- 在爬虫百度地图的期间,就为它做了一个界面,运用的是PyQt5。得到意想不到的结果:# -*- coding: utf-8 -*-# Form
- 初学者可能都会遇到一个小问题就是:在用IPython的时候,可以使用类似%matplotlib inline的Magic Function(
- 本文实例讲述了Python3将jpg转为pdf文件的方法。分享给大家供大家参考,具体如下:#coding=utf-8#!/usr/bin/e
- 一、下载anaconda第一步当然是下载anaconda了,官方网站的下载需要用迅雷才能快点,或者直接到清华大学镜像站下载。当然这里推荐脚本
- 一、输出指令ASP的输出指令<% =expression %>显示表达式的值。这个输出指令等同于使用Resp
- 二是什么时候CPU是空闲的?空闲是一个相对的标准。有时会CPU使用率30%以下可以定义为空闲;而有时候CPU使用率只有不到60%,就是空闲。
- 方法一:进入MYSQL安装目录 打开MYSQL配置文件 my.ini 或 my.cnf查找 max_connections=100 修改为
- 一、logging模块Python中有一个模块logging,可以直接记录日志# 日志级别# CRITICAL 50# ERRO