Heap / Priority Queue

目标：掌握完全二叉树上的堆序性质、数组表示、插入/删除复杂度、Priority Queue 与 Top-K 高频模式。

---

1. Heap Definition

Min Heap：

Complete Binary Tree
+
Parent <= Children

Max Heap：

Complete Binary Tree
+
Parent >= Children

因此：

Min Heap 根节点 = 整个堆最小值
Max Heap 根节点 = 整个堆最大值

Heap 不等于 BST。

BST
→ 强调整体搜索顺序
→ 左子树 < Root < 右子树

Heap
→ 强调根节点极值
→ 只要求父子之间满足堆序

Heap 不保证左右子树整体有序，也不保证中序遍历有序。

---

2. Array Representation

Heap 建立在 Complete Binary Tree 上，因此通常直接用数组保存。

从下标 0 开始：

left   = 2i + 1
right  = 2i + 2
parent = (i - 1) // 2

Heap 数组不要求整体升序或降序，只要求数组对应的完全二叉树满足堆序性质。

例如：

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

可以是合法 Min Heap，即使数组整体并非升序。

---

3. Insert: Sift Up

插入新元素：

1. 放到数组末尾，保持 Complete Binary Tree；
2. 若违反堆序，与父节点交换；
3. 不断向上直到恢复堆序。

Min Heap 中：

new < parent
→ sift up

复杂度：

O(log n)

因为最多沿树高向上移动。

---

4. Remove Top: Sift Down

删除堆顶：

1. 用最后一个节点替代根节点；
2. 删除数组最后位置；
3. 向下与更合适的子节点交换，恢复堆序。

Min Heap 中通常与更小的孩子比较和交换。

为什么使用“最后一个节点”？

真正删除最后位置后，层序数组仍连续，从而保持 Complete Binary Tree 的结构；堆序性质再通过 sift down 恢复。

不能随便删除一个叶子节点，否则可能在层序结构中留下空洞，破坏完全二叉树。

复杂度：

peek top: O(1)
push:     O(log n)
pop top:  O(log n)

---

5. Priority Queue

普通 Queue：

FIFO

Priority Queue：

每次优先处理当前最高或最低优先级元素，而不是单纯按照到达先后顺序。

Heap 是 Priority Queue 的经典底层实现。

需要区分：

Priority Queue
= 抽象需求 / ADT

Heap
= 常见实现结构

---

6. Top-K Mental Model

求最大的 K 个元素：

维护大小为 K 的 Min Heap

原因不是“最大的元素对应 Min Heap”，而是：

需要持续知道“当前 Top-K 中最小的元素”，它就是淘汰线。

新元素 x：

x <= heap top
→ x 连当前 Top-K 中最弱的元素都超过不了
→ 直接淘汰 x

x > heap top
→ 淘汰 heap top
→ 加入 x

因此：

Top K largest  → Min Heap
Top K smallest → Max Heap

核心 mental model：

Heap 保存的是淘汰线，而不是“答案方向”。

整体复杂度：

O(n log k)

当 k << n 时，比全部排序 O(n log n) 更有价值。

---

7. K-th Largest

使用大小为 K 的 Min Heap 维护最大的 K 个元素。

最终：

heap top
= 这 K 个最大元素中最小的
= 整体第 K 大

例如最大的 3 个最终是：

10, 15, 20

对应 Min Heap 根节点为 10，则：

10 = 整体第 3 大

注意：

第 K 大答案在大小为 K 的 Min Heap 的堆顶，不在叶子节点。

叶子之间没有全局大小顺序。

---

8. Python heapq

Python 标准库 heapq 默认提供 Min Heap：

import heapq

heap = []
heapq.heappush(heap, x)
x = heapq.heappop(heap)

heap[0]

表示当前 Min Heap 的最小值。

Top-K 示例：

import heapq

def top_k_largest(nums, k):
    heap = []

    for x in nums:
        if len(heap) < k:
            heapq.heappush(heap, x)
        elif x > heap[0]:
            heapq.heapreplace(heap, x)

    return heap

当前阶段只要求理解 API 与算法结构，不要求死背完整实现。

---

9. 高频场景

看到以下关键词时应对 Heap / Priority Queue 敏感：

• Top K；
• 第 K 大 / 第 K 小；
• 持续加入元素并随时查询当前极值；
• 任务优先级；
• 多路有序数据合并。

---

10. Depth Control

当前秋招阶段暂不深入：

• Fibonacci Heap；
• Binomial Heap；
• Build Heap O(n) 的严格证明；
• Heap Sort 细节；
• 高级手写 Heapify 边界技巧。

这些内容在明确 JD / 笔试需求出现前优先级低于 Graph、数据库、OS、网络及高频算法练习。

---

Review Focus

需要间隔复习：

Top K largest → size-K Min Heap
K-th largest  → Min Heap top

并通过实际题目强化：

• sift up / sift down；
• Complete Binary Tree 与数组下标关系；
• Priority Queue 场景识别；
• Top-K 的淘汰线思维。

Practice:

04_Practice/CS_MCQs/Data_Structure_Lesson_2.md

Mistakes:

05_Mistakes/CS.md

Interview QA:

06_Interview/CS_QA/Data_Structure.md