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


猜你喜欢
- 一、python压缩模块简介python直接通过内置压缩模块可以直接进行压缩文件的创建;内置模块 zipfile/rarfile 完成压缩文
- 装饰器本质上是一个 Python 函数或类,它可以让其他函数或类在不需要做任何代码修改的前提下增加额外功能,装饰器的返回值也是一个函数/类对
- 原文地址:30 Days of Mootools 1.2 Tutorials - Day 4 - Functions函数和MooTools
- 本文为大家分享了WebStorm安装教程,供大家参考一、简介WebStorm 是jetbrains公司旗下一款JavaScript 开发工具
- mtx文件是按照稀疏矩阵格式存储的矩阵数据,可以按照以下步骤读取:1、安装scanpy包pip install scanpy2、文件读取im
- 目录业务需求:方案一:vuex-persistedstate方案二:vuex-persist总结业务需求:在基于vue开发SPA项目时,为了
- 一般来说,我们会将自己写的Python模块与python自带的模块分开存放以达到便于维护的目的。那么如何在Python中添加自定义的模块呢?
- 【题目】keras中的Merge层(实现层的相加、相减、相乘)详情请参考:Merge层一、层相加keras.layers.Add()添加输入
- 1.用CSS实现布局让我们一起来做一个页面,首先,我们需要一个布局。请使用CSS控制3个div,实现如下图的布局。考察应试者的基本布局知识—
- 由于Access数据库是一种文件型数据库,所以无法跨服务器进行访问。下面我们来介绍一下如何利用SQL Server 的链接服务器,把地理上分
- 英文文档:staticmethod(function)Return a static method for function.A stati
- 本文实例讲述了Python enumerate函数功能与用法。分享给大家供大家参考,具体如下:eunmerate在英文中是列举、枚举的意思,
- 前言:目前在研究易信公众号,想给公众号增加一个获取个人交通违章的查询菜单,通过点击返回查询数据。以下是实施过程。一、首先,用火狐浏览器打开X
- 先给大家介绍下Python读取文件夹按数字排序的代码,内容如下所示:python中 os.listdir()方法用于返回指定的文件夹包含的文
- 前提条件:需要安装easy-install模块,这是一个python的模块打包工具。首先下载easy_setup.py的源代码,下载地址:
- 网上学习了的两个新方法,代码非常之简洁。看来,不是只要实现了基本功能就能交差滴,想要真的学好python还有很长的一段路呀方法一:是利用ma
- 提高SQL执行效率的几点建议:◆尽量不要在where中包含子查询;关于时间的查询,尽量不要写成:where to_char(dif_date
- 问题:如何经过convTransposed1d输出指定大小的特征?import torchfrom torch import nnimpor
- 本文实例讲述了python实现bucket排序算法。分享给大家供大家参考。具体实现方法如下:def bucketSort(a, n, buc
- 本文实例讲述了Python编程入门之Hello World的三种实现方式。分享给大家供大家参考,具体如下:第一种方式:$python>