个人中心
gpt4 book ai didi

详解Python中heapq模块的用法

转载 作者：qq735679552 更新时间：2022-09-29 22:32:09 25 4
gpt4 key购买 nike

CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.

这篇CFSDN的博客文章详解Python中heapq模块的用法由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.

heapq 模块提供了堆算法。heapq是一种子节点和父节点排序的树形数据结构。这个模块提供heap[k] <= heap[2*k+1] and heap[k] <= heap[2*k+2]。为了比较不存在的元素被人为是无限大的。heap最小的元素总是[0].

打印 heapq 类型 。

?
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
import math
import random
from cStringIO import StringIO
 
def show_tree(tree, total_width = 36 , fill = ' ' ):
    output = StringIO()
    last_row = - 1
    for i, n in enumerate (tree):
      if i:
        row = int (math.floor(math.log(i + 1 , 2 )))
      else :
        row = 0
      if row ! = last_row:
        output.write( '\n' )
      columns = 2 * * row
      col_width = int (math.floor((total_width * 1.0 ) / columns))
      output.write( str (n).center(col_width, fill))
      last_row = row
    print output.getvalue()
    print '-' * total_width
    print
    return
 
data = random.sample( range ( 1 , 8 ), 7 )
print 'data: ' , data
show_tree(data)

打印结果 。

?
1
2
3
4
5
6
7
data: [3, 2, 6, 5, 4, 7, 1]
 
      3          
   2      6     
5    4  7     1  
-------------------------
heapq.heappush(heap, item)

push一个元素到heap里, 修改上面的代码 。

?
1
2
3
4
5
6
7
8
heap = []
data = random.sample( range ( 1 , 8 ), 7 )
print 'data: ' , data
 
for i in data:
   print 'add %3d:' % i
   heapq.heappush(heap, i)
   show_tree(heap)

打印结果 。

?
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
data: [6, 1, 5, 4, 3, 7, 2]
add  6:
          6        
  ------------------------------------
add  1:
       1
    6        
------------------------------------
add  5:
       1
    6       5      
------------------------------------
add  4:
         1
     4       5      
   6
------------------------------------
add  3:
         1
     3       5      
   6    4
------------------------------------
add  7:
         1
     3        5      
   6    4    7
------------------------------------
add  2:
         1
     3        2      
   6    4    7    5
------------------------------------

根据结果可以了解，子节点的元素大于父节点元素。而兄弟节点则不会排序.

heapq.heapify(list) 。

将list类型转化为heap, 在线性时间内, 重新排列列表.

?
1
2
3
4
5
print 'data: ' , data
heapq.heapify(data)
print 'data: ' , data
 
show_tree(data)

打印结果 。

?
1
2
3
4
5
6
7
8
data: [2, 7, 4, 3, 6, 5, 1]
data: [1, 3, 2, 7, 6, 5, 4]
 
       1        
    3         2    
7    6    5    4 
------------------------------------
heapq.heappop(heap)

删除并返回堆中最小的元素, 通过heapify() 和heappop()来排序.

?
1
2
3
4
5
6
7
8
9
10
11
12
data = random.sample( range ( 1 , 8 ), 7 )
print 'data: ' , data
heapq.heapify(data)
show_tree(data)
 
heap = []
while data:
   i = heapq.heappop(data)
   print 'pop %3d:' % i
   show_tree(data)
   heap.append(i)
print 'heap: ' , heap

打印结果 。

?
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
data: [4, 1, 3, 7, 5, 6, 2]
 
          1
     4         2
   7    5    6    3
------------------------------------
 
pop  1:
          2
     4         3
   7    5    6
------------------------------------
pop  2:
          3
     4         6
   7    5
------------------------------------
pop  3:
          4
     5         6
   7
------------------------------------
pop  4:
          5
     7         6
------------------------------------
pop  5:
          6
     7
------------------------------------
pop  6:
         7
------------------------------------
pop  7:
 
------------------------------------
heap: [1, 2, 3, 4, 5, 6, 7]

可以看到已排好序的heap.

heapq.heapreplace(iterable, n) 。

删除现有元素并将其替换为一个新值.

?
1
2
3
4
5
6
7
8
9
data = random.sample( range ( 1 , 8 ), 7 )
print 'data: ' , data
heapq.heapify(data)
show_tree(data)
 
for n in [ 8 , 9 , 10 ]:
   smallest = heapq.heapreplace(data, n)
   print 'replace %2d with %2d:' % (smallest, n)
   show_tree(data)

打印结果 。

?
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
data: [7, 5, 4, 2, 6, 3, 1]
 
          1
     2         3
   5    6    7    4
------------------------------------
 
replace 1 with 8:
 
          2
     5         3
   8    6    7    4
------------------------------------
 
replace 2 with 9:
 
          3
     5         4
   8    6    7    9
------------------------------------
 
replace 3 with 10:
 
          4
     5         7
   8    6    10    9
------------------------------------

heapq.nlargest(n, iterable) 和 heapq.nsmallest(n, iterable) 。

返回列表中的n个最大值和最小值 。

?
1
2
3
4
5
6
data = range ( 1 , 6 )
l = heapq.nlargest( 3 , data)
print l     # [5, 4, 3]
 
s = heapq.nsmallest( 3 , data)
print s     # [1, 2, 3]

PS：一个计算题 构建元素个数为 K=5 的最小堆代码实例

?
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
#!/usr/bin/env python
# -*- encoding: utf-8 -*-
# Author: kentzhan
#
 
import heapq
import random
 
heap = []
heapq.heapify(heap)
for i in range ( 15 ):
  item = random.randint( 10 , 100 )
  print "comeing " , item,
  if len (heap) > = 5 :
   top_item = heap[ 0 ] # smallest in heap
   if top_item < item: # min heap
    top_item = heapq.heappop(heap)
    print "pop" , top_item,
    heapq.heappush(heap, item)
    print "push" , item,
  else :
   heapq.heappush(heap, item)
   print "push" , item,
  pass
  print heap
pass
print heap
 
print "sort"
heap.sort()
 
print heap

结果

详解Python中heapq模块的用法

最后此篇关于详解Python中heapq模块的用法的文章就讲到这里了,如果你想了解更多关于详解Python中heapq模块的用法的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。

25 4 0
文章推荐： Python中的迭代器与生成器高级用法解析
文章推荐： Python设计足球联赛赛程表程序的思路与简单实现示例
文章推荐： Python中operator模块的操作符使用示例总结
文章推荐： 基础的十进制按位运算总结与在Python中的计算示例
qq735679552
个人简介

我是一名优秀的程序员,十分优秀！

滴滴打车优惠券免费领取
滴滴打车优惠券
全站热门文章
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com