本文最后更新于:2024年1月14日 晚上

本文介绍堆和在Python内置库的实现。

简介

该模块提供了堆队列算法的实现,也称为优先级队列算法。

堆是二叉树,其中每个父节点的值小于或等于其任何子节点的值。

方法

heapify

1
heapq.heapify(x)

将列表 x 转换为线性时间内的就地堆。

1
2
3
4
5
6
a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)

-->
a
[[4, 'asdf'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

heappush

压入新元素到堆 log(n)

1
2
3
4
5
6
7
8
9
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
heapq.heappush(a, [1, 'etrfg'])

-->
a
[[1, 'etrfg'], [4, 'asdf'], [13, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf'], [7, 'asdf']]

heappop

从堆中弹出并返回最小的项,同时保持堆的不变性。

1
2
3
4
5
6
7
8
9
10
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
heapq.heappush(a, [1, 'etrfg'])
b = heapq.heappop(a)

-->
b
[1, 'etrfg']

heappushpop

在堆上推送项,然后弹出并从堆中返回最小的项。

1
2
3
4
5
6
7
8
9
10
11
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.heappushpop(a, [9, 'etrfg'])

-->
b
[4, 'asdf']
a
[[6, 'asdf'], [7, 'asdf'], [13, 'asdf'], [9, 'etrfg'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

heapreplace

先 pop 堆顶元素,再push 元素进去

1
2
3
4
5
6
7
8
9
10
11
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.heapreplace(a, [1, 'etrfg'])

-->
b
[4, 'asdf']
a
[[1, 'etrfg'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [22, 'asdf']]

merge

合并多个堆成一个

1
2
3
4
5
6
7
8
9
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.merge(a, a, a)

-->
list(b)
[[1, 'etrfg'], [1, 'etrfg'], [1, 'etrfg'], [6, 'asdf'], [6, 'asdf'], [6, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [13, 'asdf'], [7, 'asdf'], [8, 'asdf'], [13, 'asdf'], [7, 'asdf'], ...]

nlargest

返回最大的 n 个元素

1
2
3
4
5
6
7
8
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.nlargest(3, a)

-->
[[67, 'asdf'], [45, 'asdf'], [22, 'asdf']]

nsmallest

返回 n 个最小元素

1
2
3
4
5
6
7
8
9
10
import heapq

a = [[13, 'asdf'], [22, 'asdf'], [4, 'asdf'], [6, 'asdf'], [8, 'asdf'], [45, 'asdf'], [67, 'asdf'], [7, 'asdf']]
heapq.heapify(a)
b = heapq.nsmallest(3, a)


-->
b
[[4, 'asdf'], [6, 'asdf'], [13, 'asdf']]

建堆

元素需要自底向上方法建堆,底层堆建完后可以固定下来不需要根据上层堆的调整而进行调整。过程为从最后一个元素 index 向前,首先需要找到其父亲元素(index - 1) // 2 ,如果其前一个元素的父亲(index - 2) // 2是同一个节点(或者该元素是偶数下标,下标从0 开始),则他俩是兄弟,查找此三个元素中最小值,替换到父亲的位置,即完成了当前局部堆的构建,这样一路调整到数组起始位置,就完成了堆构建,时间复杂度 O(n)。

参考资料



文章链接:
https://www.zywvvd.com/notes/coding/python/python-heapq/python-heapq/


“觉得不错的话,给点打赏吧 ୧(๑•̀⌄•́๑)૭”

微信二维码

微信支付

支付宝二维码

支付宝支付

Python 堆 heapq
https://www.zywvvd.com/notes/coding/python/python-heapq/python-heapq/
作者
Yiwei Zhang
发布于
2023年8月12日
许可协议