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

时间:2022-09-15 11:14:26

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

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

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

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

看下代码:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
# 构建二叉堆
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))

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

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
# 构建二叉堆
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封装了一个堆模块, 我们使用该模块可以很高效的实现一个优先队列

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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())

具体请看heapq官网

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

原文链接:http://www.cnblogs.com/zhiyong-ITNote/archive/2017/09/28/7608330.html