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

本文实例讲述了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相关内容感兴趣的读者可查看本站专题：《Python数据结构与算法教程》、《Python加密解密算法与技巧总结》、《Python编码操作技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》及《Python入门与进阶经典教程》

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

赞 (0)

相关推荐

  • 详解字典树Trie结构及其Python代码实现

    字典树(Trie)可以保存一些字符串->值的对应关系.基本上,它跟 Java 的 HashMap 功能相同,都是 key-value 映射,只不过 Trie 的 key 只能是字符串. Trie 的强大之处就在于它的时间复杂度.它的插入和查询时间复杂度都为 O(k) ,其中 k 为 key 的长度,与 Trie 中保存了多少个元素无关.Hash 表号称是 O(1) 的,但在计算 hash 的时候就肯定会是 O(k) ,而且还有碰撞之类的问题:Trie 的缺点是空间消耗很高. 至于Trie树的实现

  • Python数据结构与算法之链表定义与用法实例详解【单链表、循环链表】

    本文实例讲述了Python数据结构与算法之链表定义与用法.分享给大家供大家参考,具体如下: 本文将为大家讲解: (1)从链表节点的定义开始,以类的方式,面向对象的思想进行链表的设计 (2)链表类插入和删除等成员函数实现时需要考虑的边界条件, prepend(头部插入).pop(头部删除).append(尾部插入).pop_last(尾部删除) 2.1 插入: 空链表 链表长度为1 插入到末尾 2.2 删除 空链表 链表长度为1 删除末尾元素 (3)从单链表到单链表的一众变体: 带尾节点的单链表

  • Python实现简单字典树的方法

    本文实例讲述了Python实现简单字典树的方法.分享给大家供大家参考,具体如下: #coding=utf8 """代码实现了最简单的字典树,只支持由小写字母组成的字符串. 在此代码基础上扩展一下,就可以实现比较复杂的字典树,比如带统计数的,或支持更多字符的字典树, 或者是支持删除等操作. """ class TrieNode(object): def __init__(self): # 是否构成一个完成的单词 self.is_word = Fal

  • Python数据结构与算法之图的最短路径(Dijkstra算法)完整实例

    本文实例讲述了Python数据结构与算法之图的最短路径(Dijkstra算法).分享给大家供大家参考,具体如下: # coding:utf-8 # Dijkstra算法--通过边实现松弛 # 指定一个点到其他各顶点的路径--单源最短路径 # 初始化图参数 G = {1:{1:0, 2:1, 3:12}, 2:{2:0, 3:9, 4:3}, 3:{3:0, 5:5}, 4:{3:4, 4:0, 5:13, 6:15}, 5:{5:0, 6:4}, 6:{6:0}} # 每次找到离源点最近的一个顶

  • Python数据结构与算法之列表（链表，linked list）简单实现

    Python 中的 list 并不是我们传统(计算机科学)意义上的列表,这也是其 append 操作会比 insert 操作效率高的原因.传统列表--通常也叫作链表(linked list)--通常是由一系列节点(node)来实现的,其每一个节点(尾节点除外)都持有一个指向下一个节点的引用. 其简单实现: class Node: def __init__(value, next=None): self.value = value self.next = next 接下来,我们就可使用链表的结构来

  • Python数据结构与算法之二叉树结构定义与遍历方法详解

    本文实例讲述了Python数据结构与算法之二叉树结构定义与遍历方法.分享给大家供大家参考,具体如下: 先序遍历,中序遍历,后序遍历 ,区别在于三条核心语句的位置 层序遍历  采用队列的遍历操作第一次访问根,在访问根的左孩子,接着访问根的有孩子,然后下一层 自左向右一一访问同层的结点 # 先序遍历 # 访问结点,遍历左子树,如果左子树为空,则遍历右子树, # 如果右子树为空,则向上走到一个可以向右走的结点,继续该过程 preorder(t): if t: print t.value preorde

  • Python数据结构与算法之图的基本实现及迭代器实例详解

    Python数据结构与算法之图的基本实现及迭代器实例详解

    本文实例讲述了Python数据结构与算法之图的基本实现及迭代器.分享给大家供大家参考,具体如下: 这篇文章参考自<复杂性思考>一书的第二章,并给出这一章节里我的习题解答. (这书不到120页纸,要卖50块!!,一开始以为很厚的样子,拿回来一看,尼玛.....代码很少,给点提示,然后让读者自己思考怎么实现) 先定义顶点和边 class Vertex(object): def __init__(self, label=''): self.label = label def __repr__(sel

  • Python数据结构与算法之图结构（Graph）实例分析

    Python数据结构与算法之图结构（Graph）实例分析

    本文实例讲述了Python数据结构与算法之图结构(Graph).分享给大家供大家参考,具体如下: 图结构(Graph)--算法学中最强大的框架之一.树结构只是图的一种特殊情况. 如果我们可将自己的工作诠释成一个图问题的话,那么该问题至少已经接近解决方案了.而我们我们的问题实例可以用树结构(tree)来诠释,那么我们基本上已经拥有了一个真正有效的解决方案了. 邻接表及加权邻接字典 对于图结构的实现来说,最直观的方式之一就是使用邻接列表.基本上就是针对每个节点设置一个邻接列表.下面我们来实现一个最简

  • Python数据结构与算法之字典树实现方法示例

    本文实例讲述了Python数据结构与算法之字典树实现方法.分享给大家供大家参考,具体如下: class TrieTree(): def __init__(self): self.root = {} def addNode(self,str): # 树中每个结点(除根节点),包含到该结点的单词数,以及该结点后面出现字母的键 nowdict = self.root for i in range(len(str)): if str[i] not in nowdict: # 发现新的组合方式 nowdi

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

    本文实例讲述了Python数据结构与算法之完全树与最小堆.分享给大家供大家参考,具体如下: # 完全树 最小堆 class CompleteTree(list): def siftdown(self,i): """ 对一颗完全树进行向下调整,传入需要向下调整的节点编号i 当删除了最小的元素后,当新增加一个数被放置到堆顶时, 如果此时不符合最小堆的特性,则需要将这个数向下调整,直到找到合适的位置为止""" n = len(self) # 当 i 节

  • Python数据结构与算法（几种排序）小结

    Python数据结构与算法(几种排序) 数据结构与算法(Python) 冒泡排序 冒泡排序(英语:Bubble Sort)是一种简单的排序算法.它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来.遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 冒泡排序算法的运作如下: 比较相邻的元素.如果第一个比第二个大(升序),就交换他们两个. 对每一对相邻元素作同样的工作,从

  • Python数据结构与算法之常见的分配排序法示例【桶排序与基数排序】

    本文实例讲述了Python数据结构与算法之常见的分配排序法.分享给大家供大家参考,具体如下: 箱排序(桶排序) 箱排序是根据关键字的取值范围1~m,预先建立m个箱子,箱排序要求关键字类型为有限类型,可能会有无限个箱子,实用价值不大,一般用于基数排序的中间过程. 桶排序是箱排序的实用化变种,其对数据集的范围,如[0,1) 进行划分为n个大小相同的子区间,每一个子区间为一个桶,然后将n非记录分配到各桶中.因为关键字序列是均匀分布在[0,1)上的,所以一般不会有很多记录落入同一个桶中. 以下的桶排序方

随机推荐