Python基础教程 集合、堆和双端队列

10.3.4 集合、堆和双端队列

有用的数据结构有很多。 Python支持一些较常用的，其中的字典（散列表）和列表（动态数组）是Python语言的有机组成部分。还有一些虽然不那么重要，但有时也能派上用场。

1. 集合

很久以前，集合是由模块sets中的Set类实现的。虽然在既有代码中可能遇到Set实例，但除非要向后兼容，否则真的没有理由再使用它。在较新的版本中，集合是由内置类set实现的，这意味着你可直接创建集合，而无需导入模块sets。

>>> set(range(10))

可使用序列（或其他可迭代对象）来创建集合，也可使用花括号显式地指定。请注意，不能仅使用花括号来创建空集合，因为这将创建一个空字典。

>>> type({})

相反，必须在不提供任何参数的情况下调用set。集合主要用于成员资格检查，因此将忽略重复的元素：

>>>

与字典一样，集合中元素的排列顺序是不确定的，因此不能依赖于这一点。

>>> {'fee', 'fie', 'foe'}

{'foe', 'fee', 'fie'}

除成员资格检查外，还可执行各种标准集合操作（你可能在数学课上学过），如并集和交集，为此可使用对整数执行按位操作的运算符（参见附录B）。例如，要计算两个集合的并集，可对其中一个集合调用方法union，也可使用按位或运算符|。

>>> a =

>>> b =

>>> a.union(b)

>>> a | b

还有其他一些方法和对应的运算符，这些方法的名称清楚地指出了其功能：

>>> c = a & b

>>> c.issubset(a)

True

>>> c

True

>>> c.issuperset(a)

False

>>> c >= a

False

>>> a.intersection(b)

>>> a & b

>>> a.difference(b)

>>> a - b

>>> a.symmetric_difference(b)

>>> a ^ b

>>> a.copy()

>>> a.copy() is a

False

另外，还有对应于各种就地操作的方法以及基本方法add和remove。有关这些方法的详细信息，请参阅“Python库参考手册”中讨论集合类型的部分。

提示 需要计算两个集合的并集的函数时，可使用set中方法union的未关联版本。这可能很有用，如与reduce一起使用。

>>> my_sets = []

>>> for i in range(10):

... my_sets.append(set(range(i, i+5)))

...

>>> reduce(set.union, my_sets)

集合是可变的，因此不能用作字典中的键。另一个问题是，集合只能包含不可变（可散列）的值，因此不能包含其他集合。由于在现实世界中经常会遇到集合的集合，因此这可能是个问题。所幸还有frozenset类型，它表示不可变（可散列）的集合。

>>> a = set()

>>> b = set()

>>> a.add(b)

Traceback (most recent call last):

File "", line 1, in ?

TypeError: set objects are unhashable

>>> a.add(frozenset(b))

构造函数frozenset创建给定集合的副本。在需要将集合作为另一个集合的成员或字典中的键时， frozenset很有用。

2. 堆

另一种著名的数据结构是堆（heap），它是一种优先队列。优先队列让你能够以任意顺序添加对象，并随时（可能是在两次添加对象之间）找出（并删除）最小的元素。相比于列表方法min，这样做的效率要高得多。

实际上， Python没有独立的堆类型，而只有一个包含一些堆操作函数的模块。这个模块名为heapq（其中的q表示队列），它包含6个函数（如表10-5所示），其中前4个与堆操作直接相关。必须使用列表来表示堆对象本身。

表10-5 模块heapq中一些重要的函数

函 数 描 述

heappush(heap, x) 将x压入堆中

heappop(heap) 从堆中弹出最小的元素

heapify(heap) 让列表具备堆特征

heapreplace(heap, x) 弹出最小的元素，并将x压入堆中

nlargest(n, iter) 返回iter中n个最大的元素

nsmallest(n, iter) 返回iter中n个最小的元素

函数heappush用于在堆中添加一个元素。请注意，不能将它用于普通列表，而只能用于使用各种堆函数创建的列表。原因是元素的顺序很重要（虽然元素的排列顺序看起来有点随意，并没有严格地排序）。

>>> from heapq import *

>>> from random import shuffle

>>> data = list(range(10))

>>> shuffle(data)

>>> heap = []

>>> forn in data:

... heappush(heap, n)

...

>>> heap

[0, 1, 3, 6, 2, 8, 4, 7, 9, 5]

>>> heappush(heap, 0.5)

>>> heap

[0, 0.5, 3, 6, 1, 8, 4, 7, 9, 5, 2]

元素的排列顺序并不像看起来那么随意。它们虽然不是严格排序的，但必须保证一点：位置i处的元素总是大于位置i // 2处的元素（反过来说就是小于位置2 * i和2 * i + 1处的元素）。这是底层堆算法的基础，称为堆特征（heap property）。

函数heappop弹出最小的元素（总是位于索引0处），并确保剩余元素中最小的那个位于索引0处（保持堆特征）。虽然弹出列表中第一个元素的效率通常不是很高，但这不是问题，因为heappop会在幕后做些巧妙的移位操作。

>>> heappop(heap)

>>> heappop(heap)

0.5

>>> heappop(heap)

1

>>> heap

[2, 5, 3, 6, 9, 8, 4, 7]

函数heapify通过执行尽可能少的移位操作将列表变成合法的堆（即具备堆特征）。如果你的堆并不是使用heappush创建的，应在使用heappush和heappop之前使用这个函数。

>>> heap = [5, 8, 0, 3, 6, 7, 9, 1, 4, 2]

>>> heapify(heap)

>>> heap

[0, 1, 5, 3, 2, 7, 9, 8, 4, 6]

函数heapreplace用得没有其他函数那么多。它从堆中弹出最小的元素，再压入一个新元素。相比于依次执行函数heappop和heappush，这个函数的效率更高。

>>> heapreplace(heap, 0.5)

>>> heap

[0.5, 1, 5, 3, 2, 7, 9, 8, 4, 6]

>>> heapreplace(heap, 10)

0.5

>>> heap

[1, 2, 5, 3, 6, 7, 9, 8, 4, 10]

至此，模块heapq中还有两个函数没有介绍： nlargest(n, iter)和nsmallest(n, iter)， :分别用于找出可迭代对象iter中最大和最小的n个元素。这种任务也可通过先排序（如使用函数sorted）再切片来完成，但堆算法的速度更快，使用的内存更少（而且使用起来也更容易）。

3. 双端队列（及其他集合）

在需要按添加元素的顺序进行删除时，双端队列很有用。在模块collections中，包含类型deque以及其他几个集合（collection）类型。

与集合（set）一样，双端队列也是从可迭代对象创建的，它包含多个很有用的方法。

>>> from collections import deque

>>> q = deque(range(5))

>>> q.append(5)

>>> q.appendleft(6)

>>> q

deque([6, 0, 1, 2, 3, 4, 5])

>>> q.pop()

5

>>> q.popleft()

6

>>> q.rotate(3)

>>> q

deque([2, 3, 4, 0, 1])

>>> q.rotate(-1)

>>> q

deque([3, 4, 0, 1, 2])

双端队列很有用，因为它支持在队首（左端）高效地附加和弹出元素，而使用列表无法这样做。另外，还可高效地旋转元素（将元素向右或向左移，并在到达一端时环绕到另一端）。双端队列对象还包含方法extend和extendleft，其中extend类似于相应的列表方法，而extendleft类似于appendleft。请注意，用于extendleft的可迭代对象中的元素将按相反的顺序出现在双端队列中。