python下实现二叉堆以及堆排序的示例

Python  /  管理员 发布于 7年前   133

堆是一种特殊的树形结构， 堆中的数据存储满足一定的堆序。堆排序是一种选择排序， 其算法复杂度， 时间复杂度相对于其他的排序算法都有很大的优势。

堆分为大头堆和小头堆， 正如其名， 大头堆的第一个元素是最大的， 每个有子结点的父结点， 其数据值都比其子结点的值要大。小头堆则相反。

我大概讲解下建一个树形堆的算法过程:

找到N/2 位置的数组数据， 从这个位置开始， 找到该节点的左子结点的索引， 先比较这个结点的下的子结点， 找到最大的那个， 将最大的子结点的索引赋值给左子结点， 然后将最大的子结点和父结点进行对比， 如果比父结点大， 与父节点交换数据。当然， 我只是大概说了下实现， 在此过程中， 还需要考虑结点不存在的情况。

看下代码：

# 构建二叉堆 def binaryHeap(arr, lenth, m):  temp = arr[m] # 当前结点的值  while(2*m+1 < lenth):  lchild = 2*m+1  if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:  lchild = lchild + 1  if temp < arr[lchild]:  arr[m] = arr[lchild]  else:  break  m = lchild  arr[m] = temp   def heapsort(arr, length):  i = int(len(arr)/2)  while(i >= 0):  binaryHeap(arr, len(arr), i)  i = i - 1   print("二叉堆的物理顺序为:")  print(arr) # 输出二叉堆的物理顺序   if __name__ == '__main__':  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]   heapsort(arr, len(arr))

堆排序过程就是依次将最后的结点与首个节点进行对比交换：

# 构建二叉堆def binaryHeap(arr, lenth, m):  temp = arr[m] # 当前结点的值  while(2*m+1 < lenth):    lchild = 2*m+1    if lchild != lenth - 1 and arr[lchild] < arr[lchild + 1]:      lchild = lchild + 1    if temp < arr[lchild]:      arr[m] = arr[lchild]    else:      break    m = lchild  arr[m] = tempdef heapsort(arr, length):  i = int(len(arr)/2)  while(i >= 0):    binaryHeap(arr, len(arr), i)    i = i - 1  print("二叉堆的物理顺序为:")  print(arr) # 输出二叉堆的物理顺序  i = length-1  while(i > 0):    arr[i], arr[0] = arr[0], arr[i] # 变量交换    binaryHeap(arr, i, 0)    i = i - 1560def pop(arr):  first = arr.pop(0)  return firstif __name__ == '__main__':  arr = [2, 87, 39, 49, 34, 62, 53, 6, 44, 98]  heapsort(arr, len(arr))  print("堆排序后的物理顺序")  print(arr) # 输出经过堆排序之后的物理顺序  data = pop(arr)  print(data)  print(arr)

python封装了一个堆模块, 我们使用该模块可以很高效的实现一个优先队列

import heapqclass Item:  def __init__(self, name):    self.name = name  def __repr__(self):    return 'Item({!r})'.format(self.name)class PriorityQueue:  def __init__(self):    self._queue = []    self._index = 0  def push(self, item, priority):    heapq.heappush(self._queue, (-priority, self._index, item)) # 存入一个三元组    self._index += 1  def pop(self):    return heapq.heappop(self._queue)[-1] # 逆序输出if __name__ == '__main__':  p = PriorityQueue()  p.push(Item('foo'), 1)  p.push(Item('bar'), 5)  p.push(Item('spam'), 4)  p.push(Item('grok'), 1)  print(p.pop())  print(p.pop())

具体请看heapq官网

以上这篇python下实现二叉堆以及堆排序的示例就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。