【python笔记】deque()、list()、heapq主要区别

内部实现

1、deque()

deque是Python中的一个双端队列，位于collections模块中。

数据结构：

deque 是一个双端队列，其内部实现基于一个双向链表。

这意味着元素不是连续存储在内存中的，而是分布在多个节点中，每个节点包含元素本身以及指向其前一个和后一个节点的链接。
动态扩容：

虽然 deque 不需要像 list 那样复制整个数组来扩容，但它仍然需要管理链表的节点，并在必要时添加新的节点。然而，这个过程的开销通常比 list 的扩容要小。
随机访问：

与 list 相比，deque 不支持快速的随机访问。访问 deque 中的元素通常需要从头或尾开始遍历链表，直到找到所需的元素，这可能需要O(n)时间复杂度。
插入和删除：

在 deque 的两端添加或删除元素是非常高效的（O(1)），因为只需要修改几个指针即可。

然而，在 deque 的中间插入或删除元素则可能较慢（O(n)），因为需要遍历链表来找到正确的位置，并可能需要移动多个节点。
 

2、list()

数据结构：

list 是一个动态数组，其内部实现基于一个连续的数组。

数组的大小可以动态变化，以容纳更多的元素。
内存分配：

当列表需要更多空间时，Python会分配一个新的、更大的数组，并将旧数组的元素复制到这个新数组中。

这个过程称为“扩容”。
随机访问：

由于列表是基于数组的，因此它支持快速的随机访问，即可以在O(1)时间复杂度内通过索引访问列表中的任意元素。
插入和删除：

在列表的末尾添加或删除元素是高效的（O(1)），但在列表的开头或中间插入或删除元素则可能较慢（O(n)），因为需要移动其他元素

3、heapq

heapq是Python中的一个模块；实际上是基于Python的列表（list）实现了一个最小堆，用于维护一组元素的优先队列。

数据结构：heapq 模块提供了一个堆队列算法的实现，它通常使用列表（list）作为底层容器。但是，heapq 并不改变列表的底层数据结构；它只是通过一系列操作（如上浮和下沉）来维护堆的属性。
堆属性：

heapq 实现的是一个最小堆（尽管可以通过一些技巧来实现最大堆），其中父节点的值不大于其子节点的值。

这使得堆顶（列表的第一个元素）始终是最小的元素。
操作：

heapq 提供了如 heappush（向堆中添加元素）、heappop（从堆中移除最小元素）和 heapify（将列表转换成堆）等函数。

这些函数通过维护堆的属性来确保堆的有效性。
性能：

heapq 的性能特点主要体现在其插入和删除操作上。

向堆中添加元素（heappush）和从堆中移除最小元素（heappop）的时间复杂度都是O(log n)，其中n是堆中的元素数量。

这是因为这些操作可能需要通过上浮或下沉来调整堆的结构。
 

使用场景

1、deque()

双端队列：

当需要在队列的两端进行频繁的插入和删除操作时，deque是理想的选择。
高效访问两端元素：

deque提供了从两端快速访问元素的能力，这使得它在某些特定场景下（如循环队列）非常有用。
队列和栈的实现：

deque可以作为队列和栈的底层实现，因为它支持从两端添加和删除元素。

2、list()

存储静态数据集：

适用于需要频繁访问元素、但不经常进行插入或删除操作的场景

3、heapq

优先队列：

当需要处理一系列元素，但每次只想处理优先级最高（或最低）的元素时，heapq非常有用。
堆排序：

heapq可以用于实现堆排序算法，这是一种基于比较的排序算法，适用于大数据集的排序。
资源分配：

在资源分配问题中，如内存管理、CPU时间片分配等，heapq可以根据优先级来分配资源。

常用方法

1、deque()与list()

共用方法
append(x)	向右侧添加一个元素
pop()	从右侧移除并返回一个元素
extend(iterable)	从右侧扩展，添加指定迭代器的元素
insert(index,obj)	在指定位置插入一个元素
index(value, [start, [stop]])	返回指定值在列表中第一次出现的索引
clear()	移除列表中的所有元素，使其长度为0
remove(value)	移除列表中第一个出现的指定值
count(value)	返回列表中指定值的出现次数
reverse()	原地翻转列表中元素
copy()	返回一个浅拷贝
deque()专用方法
appendleft(x)	向左侧添加一个元素
extendleft(iterable)	从左侧扩展deque，通过添加指定迭代器的元素（元素顺序相反）
popleft()	从左侧移除并返回一个元素
rotate(n=1)	向右旋转deque n个步骤（如果n是负数，则向左旋转）
list()专用方法
sort(key=None, reverse=False)	列表中的元素进行排序

注意：deque在两端添加或删除元素时性能更高，而list在列表中间或两端添加元素时性能相对较差，尤其是在列表很大时。

2、heapq

heappush(heap, item)	将item项添加到heap中，保持堆属性
heappop(heap)	弹出并返回heap中的最小元素（对于小顶堆）。如果堆为空，则会引发IndexError
heappushpop(heap, item)	将item推入堆中，然后弹出并返回堆中的最小元素。这个操作比先调用heappush()再调用heappop()更高效
heapreplace(heap, item)	弹出并返回堆中的最小元素，同时将item推入堆中。这个操作与先调用heappop()再调用heappush()效果相同，但更高效
heapify(list)	将列表list转换成堆。这是通过就地修改列表来完成的，意味着不会创建新列表
nlargest(n, iterable, key=None)	返回iterable中n个最大的元素。这通过保持一个大小为n的堆来实现，使得堆的根元素始终是最大的元素之一
nsmallest(n, iterable, key=None)	返回iterable中n个最小的元素。与nlargest()类似，但这是为了找到最小的元素
merge(*iterables, key=None, reverse=False)	合并多个已排序的输入为一个已排序的迭代器；这类似于sorted(itertools.chain(*iterables))，但返回的是一个迭代器，并且不会一次性加载所有数据，因此更适合于大数据集