Python堆及堆排序之heapq

Python堆及堆排序之heapq

什么是堆：堆是二叉树，最大堆中父节点大于或等于两个子节点，最小堆父节点小于或等于两个子节点。

python 中的heapq模块提供了堆排序算法的实现，具体用法如下：

• 创建堆：只有最小堆，没有最大堆，想要有最大堆的效果，可以将数据取相反数

• • heapq.heappush
• • heapq.heapify

• 访问堆内容

• • heapq.heappop
• • heapq.nlargest
• • heapq.nsmallest

• 更新/替换堆

• • heapq.heaprepalce

1. heapq.heappush & heapq.heappop

import heapq
nums = [21, 13, 52, 16, 34, 21, 119]
heap = []
for num in nums:
    heapq.heappush(heap, num)

print(heap[0])  # 弹出最小值，使用heap[0]
print([heapq.heappop(heap) for _ in range(len(nums))])  # 堆排序结果

结果：
13
[13, 16, 21, 21, 34, 52, 119]

2. heapq.heapify

import heapq
nums = [21, 13, 52, 16, 34, 21, 119]
heapq.heapify(nums)

print(nums[0])  # 弹出最小值，使用nums[0]
print([heapq.heappop(nums) for _ in range(len(nums))])  # 堆排序结果

结果：
13
[13, 16, 21, 21, 34, 52, 119]

3. heapq.heappop & heapq.nlargest & heapq.nsmallest

# heapq.heappop 参考上述代码

import heapq
nums = [21, 13, 52, 16, 34, 21, 119]

print(heapq.nlargest(3, nums))
print(heapq.nsmallest(3, nums))
结果：
[119, 52, 34]
[13, 16, 21]

# 这两个函数还接受一个参数key，用于处理dict等类型数据
score= [
    {'name': 'xiaoming', 'score': 100},
    {'name': 'xiaozhang', 'score': 90},
    {'name': 'xiaoli', 'score': 92},
    {'name': 'xiaowang', 'score': 65},
    {'name': 'xiaosun', 'score': 78}
]
print(heapq.nsmallest(3, score, key=lambda s: s['score']))
print(heapq.nlargest(3, score, key=lambda s: s['score']))
结果：
[{'score': 65, 'name': 'xiaowang'}, {'score': 78, 'name': 'xiaosun'}, {'score': 90, 'name': 'xiaozhang'}]
[{'score': 100, 'name': 'xiaoming'}, {'score': 92, 'name': 'xiaoli'}, {'score': 90, 'name': 'xiaozhang'}]

4. heapq.heaprepalce

import heapq

nums = [21, 13, 52, 16, 34, 21, 119]
heapq.heapify(nums)

heapq.heapreplace(nums, 23)
print([heapq.heappop(nums) for _ in range(len(nums))])
结果：
[16, 21, 21, 23, 34, 52, 119]