Python数据结构与算法之完全树与最小堆实例

作者:hanahimi 时间:2021-01-10 06:58:47 

本文实例讲述了Python数据结构与算法之完全树与最小堆。分享给大家供大家参考,具体如下:


# 完全树 最小堆
class CompleteTree(list):
 def siftdown(self,i):
   """ 对一颗完全树进行向下调整,传入需要向下调整的节点编号i
   当删除了最小的元素后,当新增加一个数被放置到堆顶时,
   如果此时不符合最小堆的特性,则需要将这个数向下调整,直到找到合适的位置为止"""
   n = len(self)
   # 当 i 节点有儿子(至少是左儿子时),并且有需要调整时,循环执行
   t = 0
   while i*2+1<n:
     # step 1:从当前结点,其左儿子,其右儿子中找到最小的一个,将其编号传给t
     if self[i] > self[i*2+1]:
       t = i*2+1
     else: t = i
     # 如果有右儿子,则再对右儿子进行讨论
     if i*2+2<n:
       if self[t] > self[i*2+2]: t = i*2+2
     # step 2:把最小的结点中的元素和结点i的元素交换
     if t != i:
       self[t],self[i] = self[i],self[t]
       i = t  # 更新i为刚才与它交换的儿子结点的编号,以便接下来继续向下调整
     else:
       break  # 说明当前父结点已经比两个子结点要小,结束调整
 def siftup(self,i):
   """ 对一棵完全树进行向上调整,传入一个需要向上调整的结点编号i
     当要添加一个新元素后,对堆底(最后一个)元素进行调整 """
   if i==0: return
   n = len(self)
   if i < 0: i += n
   # 注意,由于堆的特性,不需要考虑左儿子结点的情况
   # 由于父结点绝对比子结点小所以只需要比较一次
   while i!=0:
     if self[i]<self[(i-1)/2]:
       self[i],self[(i-1)/2] = self[(i-1)/2],self[i]
     else:
       break
     i = (i-1)/2   # 更新i为其父结点编号,从而便于下一次继续向上调整
 def shufflePile(self):
   """ 在当前状态下,对树调整使其成为一个堆 """
   # 从"堆底"往"堆顶"进行向下调整,使得最小的元素不断上升
   # 这样可以使得i结点以下的堆是局部最小堆
   for i in range((len(self)-2)/2,-1,-1):  # n/2,...,0
     self.siftdown(i)
 def deleteMin(self):
   """ 删除最小元素 """
   t = self[0]   # 用一个临时变量记录堆顶点的
   self[0] = self[-1] # 将堆的最后一个点赋值到堆顶
   self.pop()   # 删除最后一个元素
   self.siftdown(0)  # 向下调整
   return t
 def heapsort(self):
   """ 对堆中元素进行堆排序操作 """
   n = len(self)
   s = []
   while n>0:
     s.append(self.deleteMin())
     n -= 1
   # 由于堆中的元素已全部弹出,将排序好的元素拼接到原来的堆中
   self.extend(s)
if __name__=="__main__":
 a = [99,5,36,7,22,17,92,12,2,19,25,28,1,46]
 ct = CompleteTree(a)
 print ct
>>> [99, 5, 36, 7, 22, 17, 92, 12, 2, 19, 25, 28, 1, 46]
 ct.shufflePile()
 print ct
>>> [1, 2, 17, 5, 19, 28, 46, 12, 7, 22, 25, 99, 36, 92]
 s = ct.heapsort()
 print ct
>>> [1, 2, 5, 7, 12, 17, 19, 22, 25, 28, 36, 46, 92, 99]

希望本文所述对大家Python程序设计有所帮助。

来源:http://www.cnblogs.com/hanahimi/p/4692668.html

标签:Python,完全树
0
投稿

猜你喜欢

  • JavaScript判断变量是对象还是数组的方法

    2024-06-24 06:29:37
  • python 实现多线程下载m3u8格式视频并使用fmmpeg合并

    2022-04-18 22:15:37
  • 将python运行结果保存至本地文件中的示例讲解

    2024-01-03 04:01:52
  • MySQL8.0.26的安装与简化教程(全网最全)

    2024-01-28 11:04:17
  • 怎样在MySQL数据库中导出整个数据库

    2008-12-31 15:13:00
  • Python实现将多张图片合成视频并加入背景音乐

    2022-12-14 19:46:29
  • face++与python实现人脸识别签到(考勤)功能

    2021-10-18 09:06:06
  • Keras自定义IOU方式

    2022-12-24 07:48:27
  • asp如何让浏览器在https和http之间转化?

    2010-05-13 16:37:00
  • 详解Python进阶之切片的误区与高级用法

    2022-09-18 04:03:12
  • layui table 获取分页 limit的方法

    2023-08-24 13:44:56
  • 利用python实现后端写网页(flask框架)

    2022-06-22 04:20:50
  • python设计模式之装饰器模式

    2023-04-28 07:55:40
  • MySQL中隐藏空间问题浅析

    2009-11-24 09:04:00
  • SQL Server中通过扩展存储过程实现数据库的远程备份与恢复

    2012-05-22 18:48:56
  • MySQL如何根据不同条件联查不同表的数据if/case

    2024-01-21 14:20:10
  • MySQL实现字符串截取的图文教程

    2024-01-16 05:44:05
  • Python中根据时间自动创建文件夹的代码实现

    2023-07-06 02:42:01
  • python中字典和列表的相互嵌套问题详解

    2022-03-19 23:14:53
  • SQLServer按顺序执行多个脚本的方法(sqlcmd实用工具使用方法)

    2024-01-24 15:23:05
  • asp之家 网络编程 m.aspxhome.com