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

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

2020-12-10 00:27又见阿郎 Python

下面小编就为大家带来一篇python下实现二叉堆以及堆排序的示例。小编觉得挺不错的，现在就分享给大家，也给大家做个参考。一起跟随小编过来看看吧

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

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

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

找到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] = temp

									def 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 - 1560

									def pop(arr):

									  first = arr.pop(0)

									  return first

									if __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 heapq

									class 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())