在本篇文章里小编给大家分享的是一篇关于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);

到此这篇关于python实现堆排序的实例讲解的文章就介绍到这了,更多相关堆排序python实现内容请搜素爱安网以前的文章或下面相关文章,希望大家以后多多支持爱安网!

最新资讯
上海消保委测试网约车 超半数订单多算公里数

上海消保委测试网约车

结果显示,110次计程计时中,57次计程偏高,40次计时偏高。
掌门教育或赴美IPO 在线教育机构决战“下半场”

掌门教育或赴美IPO 在

2021年伊始,有消息称掌门教育即将赴美上市,预计募资金融
一个腾讯市值凭啥抵过六大行

一个腾讯市值凭啥抵过

腾讯之所以能为股东持续创造价值,是因为具有持续进化的
传台积电等代工厂考虑再次上调车用芯片价格最多15%

传台积电等代工厂考虑

据日(J)本(P)媒体周一晚间报道,受到全球范围内缺货潮影响,台积
腾讯投资的德国数字银行N26任命新CFO 或明年IPO

腾讯投资的德国数字银

据报道,由腾讯投资的德国数字银行N26今日宣布,任命简·
强化反垄断监管和备付金存管 强监管如何搅动支付市场

强化反垄断监管和备付

233家持牌第三方支付机构在一周内迎来了监管部门的两
最新文章
在pycharm中为项目导入anacodna环境的操作方法

在pycharm中为项目导

这篇文章主要介绍了在pycharm中为项目导入anacodna环
tensorflow的ckpt及pb模型持久化方式及转化详解

tensorflow的ckpt及pb

今天小编就为大家分享一篇tensorflow的ckpt及pb模型持
PyTorch笔记之scatter()函数的使用

PyTorch笔记之scatter

这篇文章主要介绍了PyTorch笔记之scatter()函数的使用
python3实现网页版raspberry pi(树莓派)小车控制

python3实现网页版ras

这篇文章主要为大家详细介绍了python3实现网页版raspb
完美解决pycharm导入自己写的py文件爆红问题

完美解决pycharm导入

今天小编就为大家分享一篇完美解决pycharm导入自己写
pycharm内无法import已安装的模块问题解决

pycharm内无法import

今天小编就为大家分享一篇pycharm内无法import已安装