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

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

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

# 完全树 最小堆
class CompleteTree(list):
  def siftdown(self,i):
    """ 对一颗完全树进行向下调整，传入需要向下调整的节点编号i
    当删除了最小的元素后，当新增加一个数被放置到堆顶时，
    如果此时不符合最小堆的特性，则需要将这个数向下调整，直到找到合适的位置为止"""
    n = len(self)
    # 当 i 节点有儿子（至少是左儿子时），并且有需要调整时，循环执行
    t = 0
    while i*2+1 self[i*2+1]:
 t = i*2+1
      else: t = i
      # 如果有右儿子，则再对右儿子进行讨论
      if i*2+2 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]0:
      s.append(self.deleteMin())
      n -= 1
    # 由于堆中的元素已全部d出，将排序好的元素拼接到原来的堆中
    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程序设计有所帮助。