python中的heapq库_python heapq

1.创建堆结构

这两天在学堆排序，手写建堆有两种方法。一种是从上到下从左到右，加一个数用一次heapInsert。时间复杂度是O（nlogn）。另一种方法是从下往上，从右往左，利用heapify进行调整，时间复杂度是O（n）。

而python库heapq中也有两种方法创建堆结构，本质和上述两者方法是一样的，一种用heapq.heappush(heap,arr[i]);另一种就是直接用heapq.heapify(arr)。

两种实现的方法创建的小根堆可能不一样，但都满足堆结构的特定。
此外，heapq只能快速创建小根堆，如果要创建大根堆，可以把arr中的每个数取反，然后弹出的时候再取反，就能得到从大到小的数。

import heapq
arr = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
nums = [-arr[i] for i in range(len(arr))]
# 方法一 用heappush()
heap = []
for i in range(len(arr)):
    heapq.heappush(heap, arr[i])
print("heappush", heap)

# 方法二 直接用heapq.heapify初始化
heapq.heapify(arr)
print("heapify", arr)

# 得到大根堆的效果 实际还是小根堆
print(nums)
heapq.heapify(nums)
big_to_small = [-heapq.heappop(nums) for _ in range(len(nums))]
print(big_to_small)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
'
运行
运行

得到的结果如下:

2.使用堆结构进行堆排序（小到大 大到小）

其实在去相反数得到大根堆的时候代码中已经体现了该功能。用的函数就是heaq.heappop()。

3.获取前n个最大或最小值

用的函数是nsmallest(n,arr)和nlargest(n,arr)。

# 取前k个最大最小的数
print("nsmallest", heapq.nsmallest(3, arr))
print("nlargest", heapq.nlargest(2, arr))
1
2
3

4.合并两个有序列表

使用的是heapq.merage(arr1,arr2)

a = [3, 1, 6, 8]
b = [5, 9, 2, 1]
merge = heapq.merge(sorted(a), sorted(b))
# merge返回的结果是迭代器 所以要输出list(merge)
print(list(merge))
#[1, 1, 2, 3, 5, 6, 8, 9]
1
2
3
4
5
6

5.替换数据的方法

两种方法，一种是heapq.heappushpop(heap,num),这种方法是先把num值加入到堆中，再把堆顶的元素推出。另一种是**heapq.heapreplace(heap, num)**这种方法是先把堆顶的元素推出栈然后再把值加进来。

print(heap)
gen = heapq.heappushpop(heap, 3)
print("先把3加入堆再弹出的根，弹出值：", gen)
print("after heappushpop", heap)

gen2 = heapq.heapreplace(heap, 3)
print("先弹出根在把3加入到堆中，弹出值：", gen2)
print("after heapreplace", heap)
1
2
3
4
5
6
7
8