python创建堆的方法实例讲解

时间:2022-06-12 10:25:03

1、说明

创建堆有两种基本方法:heappush() 和 heapify()。

当使用heappush()时,当新元素添加时,堆得顺序被保持了。

如果数据已经在内存中,则使用 heapify() 来更有效地重新排列列表中的元素。

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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
import heapq
from heapq_showtree import show_tree
from heapq_heapdata import data
 
heap = []
print('random :', data)
print()
 
for n in data:
  print('add {:>3}:'.format(n))
  heapq.heappush(heap, n)
  show_tree(heap)
   
# output
# random : [19, 9, 4, 10, 11]
#
# add 19:
#
#         19
# ------------------------------------
#
# add  9:
#
#         9
#     19
# ------------------------------------
#
# add  4:
#
#         4
#     19        9
# ------------------------------------
#
# add 10:
#
#         4
#     10        9
#   19
# ------------------------------------
#
# add 11:
#
#         4
#     10        9
#   19    11
# ------------------------------------

知识点扩展:

创建最大(小)堆

二叉堆本质上是一种完全二叉树,存储方式并不是链式存储,而是顺序存储

堆操作:插入(叶子节点上调),删除(堆顶元素下沉)

堆创建:非叶子节点下沉(从最后一个非叶子节点开始)

最小堆:

最小堆任何一个父节点的值,都小于等于它左右孩子节点的值

创建过程:如果非叶子节点值大于其子节点,将其下沉

最大堆:

最大堆任何一个父节点的值,都大于等于它左右孩子节点的值。

创建过程:如果非叶子节点值小于其子节点,将其下沉

到此这篇关于python创建堆的方法实例讲解的文章就介绍到这了,更多相关python创建堆的方法有哪些内容请搜索服务器之家以前的文章或继续浏览下面的相关文章希望大家以后多多支持服务器之家!

原文链接:https://www.py.cn/jishu/jichu/27955.html