QingZhi's Blog

Persistence is not easy

0%

Python_heapq类

Posted on Edited on In , Views: Valine:

Python官方提供的最小堆类:

官方文档

博客

heapq类是什么

  1. heapq本身是heap queue algorithm的缩略简称。

  2. 是Python官方提供的最小堆类

    • 提供了常见的操作函数
    • 易于实现堆排序，优先队列等应用

初始化与相关函数介绍

堆的初始化

堆实质就是一种理论上为树，物理上为列表的一种数据结构。

1
2
3
4
5
6
7
8
9
10
11
12
# 构建一个空堆就是一个空列表
emptyHeap = []

# 构建一个非空堆利用 heap.heapify()

originalList = [i for i in range(100 , 0 , -8)]
print("Before heapify: ",originalList)
heapq.heapify(originalList) # 注意heap.heapify()方法原地修改了list对象，而没有返回一个新的列表
print("After heapify: ",originalList)

# Before heapify:  [100, 92, 84, 76, 68, 60, 52, 44, 36, 28, 20, 12, 4]
# After heapify:  [4, 20, 12, 36, 28, 60, 52, 44, 76, 92, 68, 84, 100]

函数介绍

函数名称 函数作用
heapq.heappush(heap,item) 堆插入，并进行堆调整（保持了最小堆）
heapq.heappop(heap) pop堆顶元素，并返回，进行堆调整（保持了最小堆）
heapq.heappushpop(heap,item) 先push然后pop堆顶元素，并返回此元素，进行堆调整
heapq.heapify(x) 将list列表转换为最小堆
heapq.heapreplace(heap,item) 先pop，返回了此元素 ， 然后push item元素，进行堆调整
heapq.merge(*iterables , key= None , reverse = False) 合并多个堆，并返回结果
heapq.nlargest(n ,iterable , key=None) 返回可迭代对象的前N个大的元素，从大到小排序
heapq.nsmallest(n , iterable , key=None) 返回可迭代对象的前N个小的元素，从小到大排序

函数功能简单展示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import heapq
import random
originalList = [i for i in range(100 , 0 , -8)]
print("Before heapify: ",originalList)
heapq.heapify(originalList)
print("After heapify: ",originalList)
heapq.heappush(originalList , 1)
print("After heappush: " , originalList)
smallest = heapq.heappop(originalList)
print("smallest elements is: " , smallest)
secondSmall = heapq.heappushpop(originalList , 1000)
print("After heappushpop", originalList)
print("second small element is: " , secondSmall)
secondSmall = heapq.heapreplace(originalList , 45)
print("After heapreplace", originalList)
print("second small element is: " , secondSmall)
print("top 3 big elements is: " , heapq.nlargest(3,originalList))
print("top 3 small elements is:", heapq.nsmallest(3,originalList))
1
2
3
4
5
6
7
8
9
10
Before heapify:  [100, 92, 84, 76, 68, 60, 52, 44, 36, 28, 20, 12, 4]
After heapify:  [4, 20, 12, 36, 28, 60, 52, 44, 76, 92, 68, 84, 100]
After heappush:  [1, 20, 4, 36, 28, 60, 12, 44, 76, 92, 68, 84, 100, 52]
smallest elements is:  1
After heappushpop [12, 20, 52, 36, 28, 60, 1000, 44, 76, 92, 68, 84, 100]
second small element is:  4
After heapreplace [20, 28, 52, 36, 45, 60, 1000, 44, 76, 92, 68, 84, 100]
second small element is:  12
top 3 big elements is:  [1000, 100, 92]
top 3 small elements is: [20, 28, 36]

堆排序

1
2
3
4
5
6
from heapq import heappop , heappush
def heapsort(iterable):
     h = []
     for value in iterable:
         heappush(h, value)
     return [heappop(h) for i in range(len(h))]
1
2
heapsort([1,3,5,7,9,2,4,6,8,0])
#[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]