1
插入 85 到最大堆 [90, 80, 70, 50, 60, 30, 40]：
2

3
Step 1: 追加到末尾
4
  [90, 80, 70, 50, 60, 30, 40, 85]
5
                                 ↑ 新元素 (index=7)
6

7
Step 2: 上浮——与父节点比较，如果更大就交换
8
  85 vs parent=50 (index=3)  →  85 > 50 → swap!
9
  [90, 80, 70, 85, 60, 30, 40, 50]
10

11
  85 vs parent=80 (index=1)  →  85 > 80 → swap!
12
  [90, 85, 70, 80, 60, 30, 40, 50]
13

14
  85 vs parent=90 (index=0)  →  85 < 90 → 停！
15

16
最终: [90, 85, 70, 80, 60, 30, 40, 50]

1
删除最大值（堆顶 90）：
2

3
Step 1: 用末尾元素替换堆顶
4
  [50, 85, 70, 80, 60, 30, 40]
5
   ↑ 50 不应该在这里
6

7
Step 2: 下沉——与较大的子节点比较，如果更小就交换
8
  50 vs max(left=85, right=70) = 85  →  50 < 85 → swap!
9
  [85, 50, 70, 80, 60, 30, 40]
10

11
  50 vs max(left=80, right=60) = 80  →  50 < 80 → swap!
12
  [85, 80, 70, 50, 60, 30, 40]
13

14
  50 没有子节点了 → 停！
15

16
最终: [85, 80, 70, 50, 60, 30, 40]

1
template <typename T, typename Compare = std::less<T>>
2
class BinaryHeap {
3
    std::vector<T> _data;
4
    Compare _cmp;  // 默认 less → 最大堆（父 > 子）
5

6
    // ===== 辅助 =====
7
    int _parent(int i) const { return (i - 1) / 2; }
8
    int _left(int i) const   { return 2 * i + 1; }
9
    int _right(int i) const  { return 2 * i + 2; }
10

11
    // ===== 上浮 =====
12
    void _sift_up(int i) {
13
        while (i > 0 && _cmp(_data[_parent(i)], _data[i])) {
14
            // 父 < 子（违反堆序）→ 交换
15
            std::swap(_data[_parent(i)], _data[i]);
16
            i = _parent(i);
17
        }
18
    }
19

20
    // ===== 下沉 =====
21
    void _sift_down(int i) {
22
        int n = _data.size();
23
        while (true) {
24
            int largest = i;
25
            int l = _left(i);
26
            int r = _right(i);
27

28
            if (l < n && _cmp(_data[largest], _data[l]))
29
                largest = l;
30
            if (r < n && _cmp(_data[largest], _data[r]))
31
                largest = r;
32

33
            if (largest == i) break;  // 已满足堆序
34

35
            std::swap(_data[i], _data[largest]);
36
            i = largest;
37
        }
38
    }
39

40
public:
41
    BinaryHeap() = default;
42

43
    // 从数组建堆 → O(n)
44
    BinaryHeap(std::vector<T> data) : _data(std::move(data)) {
45
        // 自底向上 sift-down
46
        for (int i = static_cast<int>(_data.size()) / 2 - 1; i >= 0; --i) {
47
            _sift_down(i);
48
        }
49
    }
50

51
    // 插入 → O(log n)
52
    void push(const T& val) {
53
        _data.push_back(val);
54
        _sift_up(_data.size() - 1);
55
    }
56

57
    // 取堆顶 → O(1)
58
    const T& top() const { return _data.front(); }
59

60
    // 弹出堆顶 → O(log n)
61
    void pop() {
62
        _data.front() = _data.back();
63
        _data.pop_back();
64
        if (!_data.empty()) _sift_down(0);
65
    }
66

67
    std::size_t size() const { return _data.size(); }
68
    bool empty() const { return _data.empty(); }
69
};

1
#include <queue>
2

3
// 最大堆（默认）
4
std::priority_queue<int> max_pq;
5
max_pq.push(3);
6
max_pq.push(1);
7
max_pq.push(4);
8
max_pq.top();  // 4
9
max_pq.pop();  // 弹出 4
10

11
// 最小堆（传 greater）
12
std::priority_queue<int, std::vector<int>, std::greater<int>> min_pq;
13
min_pq.push(3);
14
min_pq.push(1);
15
min_pq.push(4);
16
min_pq.top();  // 1
17

18
// 自定义比较
19
auto cmp = [](const auto& a, const auto& b) { return a.cost > b.cost; };
20
std::priority_queue<Edge, std::vector<Edge>, decltype(cmp)> pq(cmp);

1
#include <algorithm>
2
#include <vector>
3

4
std::vector<int> v = {3, 1, 4, 1, 5, 9, 2, 6};
5

6
// 建堆 → O(n)
7
std::make_heap(v.begin(), v.end());
8
// v = [9, 6, 4, 1, 5, 3, 2, 1]
9

10
// 入堆 → 先 push_back，再 push_heap → O(log n)
11
v.push_back(8);
12
std::push_heap(v.begin(), v.end());
13
// v = [9, 8, 4, 6, 5, 3, 2, 1, 1]
14

15
// 出堆 → 先 pop_heap（把最大值换到末尾），再 pop_back → O(log n)
16
std::pop_heap(v.begin(), v.end());
17
v.pop_back();
18
// v = [8, 6, 4, 1, 5, 3, 2, 1]
19

20
// 堆排序 → O(n log n)
21
std::sort_heap(v.begin(), v.end());
22
// v = [1, 1, 2, 3, 4, 5, 6, 8]
23

24
// 检查是否是堆
25
bool is_heap = std::is_heap(v.begin(), v.end());

1
void heapSort(std::vector<int>& arr) {
2
    int n = arr.size();
3

4
    // Step 1: 建堆（自底向上 sift-down）
5
    for (int i = n / 2 - 1; i >= 0; --i) {
6
        _siftDown(arr, n, i);
7
    }
8

9
    // Step 2: 逐个取出最大值
10
    for (int i = n - 1; i > 0; --i) {
11
        std::swap(arr[0], arr[i]);  // 最大值放末尾
12
        _siftDown(arr, i, 0);       // 缩小堆范围，修复堆顶
13
    }
14
}
15

16
void _siftDown(std::vector<int>& arr, int heap_size, int i) {
17
    while (true) {
18
        int largest = i;
19
        int l = 2 * i + 1;
20
        int r = 2 * i + 2;
21

22
        if (l < heap_size && arr[l] > arr[largest]) largest = l;
23
        if (r < heap_size && arr[r] > arr[largest]) largest = r;
24

25
        if (largest == i) break;
26

27
        std::swap(arr[i], arr[largest]);
28
        i = largest;
29
    }
30
}

1
int findKthLargest_quick(std::vector<int>& nums, int k) {
2
    // 第 k 大 = 第 (n-k) 小 (0-indexed)
3
    int target = nums.size() - k;
4
    return _quickSelect(nums, 0, nums.size() - 1, target);
5
}
6

7
int _quickSelect(std::vector<int>& nums, int lo, int hi, int target) {
8
    int pivot = nums[lo + rand() % (hi - lo + 1)];
9
    int i = lo, j = lo, k = hi;
10

11
    // 三路划分：[< pivot | == pivot | > pivot]
12
    while (j <= k) {
13
        if (nums[j] < pivot) std::swap(nums[i++], nums[j++]);
14
        else if (nums[j] > pivot) std::swap(nums[j], nums[k--]);
15
        else ++j;
16
    }
17

18
    if (target < i) return _quickSelect(nums, lo, i - 1, target);
19
    if (target > k) return _quickSelect(nums, k + 1, hi, target);
20
    return nums[target];
21
}
22
// 时间 O(n) 平均, O(n²) 最坏; 空间 O(1)

1
Step 1: 暴力想法
2
  每次 addNum 插入排序数组, findMedian 取中间 → addNum O(n), findMedian O(1)
3
  或者: addNum O(1) 直接追加, findMedian 时排序取中间 → findMedian O(n log n)
4
  都太慢。
5

6
Step 2: 目标复杂度
7
  addNum O(log n), findMedian O(1) → 需要始终维护"有序性的部分信息"
8

9
Step 3: 关键洞察
10
  中位数把数据分成"较小的一半"和"较大的一半"。
11
  我不需要两半各自完全有序, 只需要知道:
12
    - 较小半的最大值 (小半里最接近中间的)
13
    - 较大半的最小值 (大半里最接近中间的)
14

15
  "最大值" → 最大堆!  "最小值" → 最小堆!
16

17
Step 4: 双堆方案
18
  最大堆 lo: 存较小的一半 (堆顶 = 小半的最大值)
19
  最小堆 hi: 存较大的一半 (堆顶 = 大半的最小值)
20

21
  保持: lo.size() == hi.size() 或 lo.size() == hi.size() + 1
22
  中位数: lo.size() > hi.size() → lo.top()
23
           否则 → (lo.top() + hi.top()) / 2
24

25
Step 5: 插入逻辑
26
  新数先入 lo → lo 的最大值转入 hi → 如果 hi 多了再转回 lo
27
  这 3 步保证: lo 的每个元素 ≤ hi 的每个元素, 且大小平衡

1
class MedianFinder {
2
    // 最大堆：存较小的一半（堆顶 = 较小半的最大值）
3
    std::priority_queue<int> lo;
4
    // 最小堆：存较大的一半（堆顶 = 较大半的最小值）
5
    std::priority_queue<int, std::vector<int>, std::greater<int>> hi;
6

7
public:
8
    void addNum(int num) {
9
        lo.push(num);                // 先放入较小半
10
        hi.push(lo.top());           // 把最大值转到较大半
11
        lo.pop();
12

13
        // 保持 lo.size() >= hi.size()（lo 可以多一个）
14
        if (lo.size() < hi.size()) {
15
            lo.push(hi.top());
16
            hi.pop();
17
        }
18
    }
19

20
    double findMedian() {
21
        if (lo.size() > hi.size()) {
22
            return lo.top();  // 奇数个 → lo 堆顶
23
        }
24
        return (lo.top() + hi.top()) / 2.0;  // 偶数个 → 两堆顶的均值
25
    }
26
};
27
// addNum: O(log n), findMedian: O(1)

1
ListNode* mergeKLists(std::vector<ListNode*>& lists) {
2
    auto cmp = [](ListNode* a, ListNode* b) { return a->val > b->val; };
3
    std::priority_queue<ListNode*, std::vector<ListNode*>, decltype(cmp)> pq(cmp);
4

5
    // 把每个链表的头节点放入最小堆
6
    for (auto* head : lists) {
7
        if (head) pq.push(head);
8
    }
9

10
    ListNode dummy(0);
11
    ListNode* tail = &dummy;
12

13
    while (!pq.empty()) {
14
        ListNode* node = pq.top();
15
        pq.pop();
16

17
        tail->next = node;
18
        tail = node;
19

20
        if (node->next) pq.push(node->next);
21
    }
22

23
    return dummy.next;
24
}
25
// 时间 O(N log k), N = 总节点数, k = 链表数
26
// 空间 O(k)

1
std::vector<int> topKFrequent(std::vector<int>& nums, int k) {
2
    // 1. 统计频率
3
    std::unordered_map<int, int> freq;
4
    for (int n : nums) ++freq[n];
5

6
    // 2. 最小堆维护 top-k
7
    auto cmp = [](const auto& a, const auto& b) { return a.second > b.second; };
8
    std::priority_queue<std::pair<int,int>, std::vector<std::pair<int,int>>,
9
                        decltype(cmp)> pq(cmp);
10

11
    for (auto& [num, count] : freq) {
12
        pq.push({num, count});
13
        if (static_cast<int>(pq.size()) > k) pq.pop();
14
    }
15

16
    // 3. 提取结果
17
    std::vector<int> result;
18
    while (!pq.empty()) {
19
        result.push_back(pq.top().first);
20
        pq.pop();
21
    }
22
    return result;
23
}
24
// 时间 O(n log k), 空间 O(n)

1
std::vector<std::vector<int>> kClosest(
2
    std::vector<std::vector<int>>& points, int k)
3
{
4
    // 最大堆维护最近 k 个（堆顶 = 第 k 近 = k 个中最远的）
5
    auto dist = [](const std::vector<int>& p) {
6
        return p[0] * p[0] + p[1] * p[1];  // 不用开方，比较平方即可
7
    };
8

9
    auto cmp = [&](const std::vector<int>& a, const std::vector<int>& b) {
10
        return dist(a) < dist(b);  // 最大堆
11
    };
12

13
    std::priority_queue<std::vector<int>, std::vector<std::vector<int>>,
14
                        decltype(cmp)> pq(cmp);
15

16
    for (auto& p : points) {
17
        pq.push(p);
18
        if (static_cast<int>(pq.size()) > k) pq.pop();
19
    }
20

21
    std::vector<std::vector<int>> result;
22
    while (!pq.empty()) {
23
        result.push_back(pq.top());
24
        pq.pop();
25
    }
26
    return result;
27
}
28
// 时间 O(n log k), 空间 O(k)