数据结构

复杂度速查

数据结构	操作	时间复杂度
列表	索引访问/切片	O(1) / O(k)
	append/pop(末尾)	O(1)
	insert/pop(开头)	O(n)
	in 检查	O(n)
集合/字典	in 检查	O(1) 平均
	add/insert	O(1) 平均
	remove/delete	O(1) 平均
堆	push/pop	O(log n)
	查看最值	O(1)
排序	sort/sorted	O(n log n)
遍历	所有元素	O(n)

注：集合/字典的 O(1) 是平均情况，最坏情况可能为 O(n)

堆（优先队列）

import heapq
heap = []              # 小顶堆（Python 只有小顶堆）
heapq.heapify(heap)   # 转堆
heapq.heappush(heap, x)  # 插入
heapq.heappop(heap)    # 弹出最小值
heap[0]               # 查看最小值
heapq.heapreplace(heap, x)  # 弹出+插入（原子操作）
# 大顶堆：存负值
heapq.heappush(heap, -x)
x = -heapq.heappop(heap)  # 取出时再取负，得到原值

房间分配（优先队列）

# 最少房间数：按到达时间排序，用小顶堆存储离开时间
def min_rooms(timetable):
    timetable.sort()  # 按到达时间排序
    heap = []
    for arrival, departure in timetable:
        if heap and arrival > heap[0]:  # 有房间空出
            heapq.heapreplace(heap, departure)
        else:  # 需要新房间
            heapq.heappush(heap, departure)
    return len(heap)

求 Top K 大元素：

def top_k(arr, k):
    heap = arr[:k]
    heapq.heapify(heap)
    for x in arr[k:]:
        if x > heap[0]:
            heapq.heapreplace(heap, x)
    return sorted(heap, reverse=True)

合并 K 个有序数组：

def merge_sorted_arrays(arrays):
    result = []
    heap = [(arr[0], i, 0) for i, arr in enumerate(arrays) if arr]
    heapq.heapify(heap)
    while heap:
        val, i, j = heapq.heappop(heap)
        result.append(val)
        if j + 1 < len(arrays[i]):
            heapq.heappush(heap, (arrays[i][j+1], i, j+1))
    return result