python实现堆排序的实例讲解

作者:阿凯 时间:2023-01-06 20:50:38 

堆排序

堆是一种完全二叉树(是除了最后一层,其它每一层都被完全填充,保持所有节点都向左对齐),首先需要知道概念:最大堆问题,最大堆就是根节点比子节点值都大,并且所有根节点都满足,那么称它为最大堆。反之最小堆。

当已有最大堆,如下图,首先将7提出,然后将堆中最后一个元素放到顶点上,此时这个堆不满足最大堆了,那么我们要给它构建成最大堆,需要找到此时堆中对打元素然后交换,此时最大值为6,符合最大堆后,我们将6提取出来,然后将堆中最后一个元素放到堆的顶部...以此类推。最后提取的数值7,6,5,4,3,2,1

python实现堆排序的实例讲解

那么在维护一个最大堆过程中,最多进行交换次数决定了此算法复杂度,但交换次数与树的高度有关:

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
0
投稿

猜你喜欢

  • MySQL Enterprise备份的恢复解决方案

    2011-12-14 18:36:25
  • 教你轻松掌握如何保护MySQL中的重要数据

    2008-12-19 17:42:00
  • 通过python改变图片特定区域的颜色详解

    2021-09-17 11:01:22
  • Python网络编程 Python套接字编程

    2022-06-09 09:41:32
  • python的几种开发工具介绍

    2021-09-28 01:54:44
  • numpy之sum()的使用及说明

    2023-12-12 00:31:16
  • JS+CSS实现的日本门户网站经典选项卡导航效果

    2023-09-04 03:40:24
  • Python学习小技巧总结

    2021-09-21 09:28:49
  • 吴恩达机器学习练习:SVM支持向量机

    2023-10-30 11:49:53
  • Python内置方法和属性应用:反射和单例(推荐)

    2022-08-04 03:23:48
  • Python利用os模块实现自动删除磁盘文件

    2023-04-06 17:04:37
  • asp之自动闭合HTML/ubb标签函数附简单注释

    2011-04-04 11:18:00
  • asp无组件上传并插入到数据库里

    2008-10-24 10:04:00
  • 基于Python编写一个简单的服务注册发现服务器

    2022-06-11 20:23:31
  • Gradio机器学习模型快速部署工具quickstart

    2023-06-30 01:09:52
  • Python逐行读取文件中内容的简单方法

    2023-03-02 16:01:09
  • 使用python实现excel的Vlookup功能

    2023-05-01 20:15:15
  • tensorflow 保存模型和取出中间权重例子

    2021-05-11 07:30:11
  • asp如何向前端显示用户请求的信息?

    2010-06-09 18:52:00
  • Python实现从多表格中随机抽取数据

    2022-07-01 01:58:18
  • asp之家 网络编程 m.aspxhome.com