8. Python3 中的数据结构

Python更多的数据结构

• 集合（set）
• 堆（heap）
• 双向队列（double-ended queue）

在Python内置的数据类型中，tuple，string，list，dict这四种传统的数据类型基本上够用了，可还是不够灵活高效。可变数据类型只有list和dict两种，dict的键值对应的表达也太死板，所以在list的基础上衍生出来了set、heap、deque等高级丢丢的数据结构（当然功能也更加细化）。

---

8.1. 集合 set

没有重复元素，不能使用索引访问的数据结构哦，支持集合操作（交intersection、并union、差difference、对称差symmetric_difference）。不恰当的比喻，集合就是一个大罐子。

1. 与list的关系。set（lst）将列表转换成set；list（st）将set转换成list对象。
2. 元素的加入：add（st，value）
3. 元素的删除（remove，指定元素）和弹出（pop，最小元素）

8.2 堆 heap

python中的堆 是一种按照某种顺序排列的数据结构（比喻为水桶，最轻的水果飘在最上面）。加入一个元素后自动排序，剔除一个元素也自动排序。加入值相当与lst.append().sort()，读取值相当与lst[0] . 简单的说，heap= list+sort

1. 与list的关系。heap就是一种特殊排序的list（heap是基于树的排序），可通过heapify(lst)强制将list转换成heap（注意，未排序，只是可以用后面的heapq模块中的函数操作了）
2. 由于不存在heap数据结构的对象，所以正常的堆(heap)的操作都需要将heap作为参数传入函数（list的所有操作，堆heap均可用，只是会破坏其排序结构）。

>>> from heapq import *
>>> from _heapq import heappop
>>> heap =[] # an empty list, is also a heap
>>> for i in range(10):
...     heappush(heap,10-i) #  push a value
... 
>>> print(heap)
[1, 2, 5, 4, 3, 9, 6, 10, 7, 8]
>>> heappop(heap)          # pop the minimal value
1
>>> print(heap)
[2, 3, 5, 4, 8, 9, 6, 10, 7]
>>> heapreplace(heap,6.5) # pop at first, and push another value
2
>>> print(heap)
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> type(heap) # heap is a list in the implementation
<class 'list'>

3. 更多操作，最大(小)的n个值

>>> heap
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]
>>> nlargest(3,heap) # 返回最大的多个值
[10, 9, 8]
>>> nsmallest(2,heap)# 返回最小的n个值
[3, 4]
>>> heap                    # 不是 inplace操作，heap没变
[3, 4, 5, 6.5, 8, 9, 6, 10, 7]

8.3 双端队列（double-ended queue）

我理解为管道操作，可以两边塞，也可以两边掏。像list一样从中间取一个值，当然可以（如果你非常想要这么做，这不是queue的主要职责）！

>>> from collections import deque
>>> q = deque(list(range(6)))
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.append('x') 
>>> q.appendleft('-1')
>>> print(q)
deque(['-1', 0, 1, 2, 3, 4, 5, 'x'])
>>> print(q.pop())
x
>>> print(q.popleft())
-1
>>> print(q)
deque([0, 1, 2, 3, 4, 5])
>>> q.rotate(3)
>>> print(q)
deque([3, 4, 5, 0, 1, 2])
>>> q.rotate(-1)
>>> print(q)
deque([4, 5, 0, 1, 2, 3])
>>> type(q)
<class 'collections.deque'>
>>> q[2] = 10
>>> print(q)
deque([4, 5, 10, 1, 2, 3])

小节

• 针对list的各种不足，提出了set，heap，deque三种新的数据结构。
• set能够有效剔除重复数据，同是提供了一套的集合的逻辑操作运算（用的很多，但是自己用list实现是很麻烦的事情）。
• heap 在与动态更新list数据的时候能够很快的给出排序结果，也就是在push的时候数据的放置位置是按照大小判定的。
• deque 内在实现就是list，除了操作的便捷性以外（这就够了，不然纯c的天下何须python），我没有发现特别的优势。