Week 5 学习成果｜Stack、Queue 与 MinHeap

本篇与一年学习计划总纲 Phase I 的 Week 5 · 常用数据结构 一致，按总纲「每周固定执行模板」编排。Week 5 暂无单独的计划篇，本篇先记录实际成果。

🎯 本周目标

L2

• ✅ 手写 Stack、Queue、简化 MinHeap
• ✅ 能解释为什么 Top-K 通常不必对全部数据排序

📚 Core Knowledge

• Stack（LIFO）、Queue（FIFO）
• Heap / Priority Queue、MinHeap 的数组表示
• 用堆做 Top-K、频率排名、LRU Cache

✍️ Human Core

• 手写 Stack（基于 list 尾部）
• 手写 Queue（基于 collections.deque）
• 手写简化 MinHeap

🤖 AI Build

• Top-K
• 频率排名
• LRU Cache

🧪 Experiment

Hypothesis

• 只保留大小 k 的堆来选 Top-K，比先把全部数据排序再取前 k 更省。

Experiment

• 比较「全排序取前 k」与「维护大小 k 的堆」两种 Top-K 实现。

Result

• 全排序为 O(n log n)；堆做法只需在 n 个元素上各做一次 O(log k) 的调整，约 O(n log k)。

Conclusion

• k 远小于 n 时，堆做法更划算；这正是 Top-K 不必对全部数据排序的原因。

📝 数智工程师考试映射

• 栈、队列的语义与应用
• 堆与优先队列
• Top-K 与复杂度取舍

✅ Acceptance

• 能解释为什么 Top-K 通常不必对全部数据排序
• 能说清 MinHeap 的 push / pop 为什么是 O(log n)

🧠 本周最重要的问题

为什么 Top-K 不用把全部数据排完？

因为只关心前 k 个。维护一个大小 k 的堆，每来一个元素最多做一次 O(log k) 的调整，整体约 O(n log k)；对全部数据排序则是 O(n log n)。k 越小，省得越多。

❓ 尚未解决

• 写一个完整、不依赖参考的 LRU（dict + 双向链表）还没做到。
• heapq 只能做小顶堆，取 Top-K 时要取负或用元组技巧，还没整理成顺手的小抄。

📊 Final Level

L2

Stack（LIFO）

后进先出，用 list 尾部操作最自然：

stack = []
stack.append(1)     # push，均摊 O(1)
top = stack.pop()   # pop，O(1)

Queue（FIFO）

先进先出。用 list 头删是 O(n)（后面元素整体前移），改用 collections.deque 两端都是 O(1)：

from collections import deque
q = deque()
q.append(1)         # 入队
first = q.popleft() # 出队，O(1)

MinHeap

用数组存完全二叉树，父子下标按 2i+1 / 2i+2 / (i-1)//2 换算；push / pop 都是 O(log n)，取最小值 O(1)。Python 用 heapq（默认小顶堆）：

import heapq
h = [3, 1, 5]
heapq.heapify(h)          # O(n) 建堆
heapq.heappush(h, 2)      # O(log n)
smallest = heapq.heappop(h)  # O(log n)

应用

• Top-K：维持大小 k 的堆，整体约 O(n log k)。
• 频率排名：先统计频次，再用堆取前 N。
• LRU Cache：哈希表 + 双向链表，实现 O(1) 的访问与淘汰；OrderedDict 可更省事地模拟。

来源与延伸阅读

• Python collections（deque）
• heapq — 堆队列算法