向上调整需确保i>0再算父节点索引，用有符号int防绕回；向下调整须先判left
向上调整 heapify_up 怎么写才不越界
向上调整发生在插入新元素后，把新节点从堆底一路“浮”到合适位置。关键不是“怎么比较”，而是**索引计算必须防越界**——父节点索引是 (i - 1) / 2，但当 i == 0（已在根）时必须立即停止。
常见错误是写成 while (i > 0 && arr[i] > arr[(i-1)/2]) 却忘了在循环体内更新 i 后没检查新 i 是否仍合法；更隐蔽的坑是用无符号整数（如 size_t i），i - 1 会绕回极大值，直接崩。
- 始终用有符号整型（如
int）作下标变量 - 循环条件严格写成
i > 0，且更新i后不依赖后续判断来兜底 - 比较前不假设父节点存在——
i > 0就是唯一安全前提
void heapify_up(vector& heap, int i) { while (i > 0) { int parent = (i - 1) / 2; if (heap[i] <= heap[parent]) break; // 小顶堆：子不小于父则停 swap(heap[i], heap[parent]); i = parent; } }
向下调整 heapify_down 的三个子节点边界判断
向下调整用于弹出堆顶或修改根后，把顶部元素“沉”到底部。难点不在逻辑，而在**左右子节点索引是否越界**：左子为 2*i + 1，右子为 2*i + 2，但这两个索引随时可能 ≥ heap.size()。
不能只写 if (left heap[largest]) 就完事——如果 left 已越界，right 就不该参与比较；更糟的是，有些实现先算 right 再判断，导致 right 计算本身越界（尤其用无符号类型）。
立即学习“C++免费学习笔记（深入）”；
- 先算
left = 2*i + 1，若left >= size，直接退出（无子节点） - 再算
right = left + 1，仅当right 才和left比较选大者 - 选中的最大子节点必须和当前节点比较，且
swap后要继续向下，不能漏掉深层调整
void heapify_down(vector& heap, int i, int size) { while (true) { int largest = i; int left = 2 * i + 1; if (left < size && heap[left] > heap[largest]) largest = left; int right = left + 1; if (right < size && heap[right] > heap[largest]) largest = right; if (largest == i) break; swap(heap[i], heap[largest]); i = largest; } }
std::priority_queue 底层真用 vector + 手动调整吗
是的，std::priority_queue 默认容器是 std::vector，默认比较器是 std::less（大顶堆），所有插入、弹出都靠隐式调用 push_heap / pop_heap，而这两个函数底层就是你写的 heapify_up 和 heapify_down 的泛型版本。
但它不直接暴露调整函数——你无法对已有 vector 调用 make_heap 后再手动调用 push_heap，除非你用原始数组或迭代器区间。实际项目中，如果需要中途修改某个元素并重平衡，priority_queue 无能为力，必须自己维护 vector + 下标映射 + 手动调整。
-
priority_queue的top()是O(1)，push()和pop()都是O(log n) - 它不提供“降低/升高某元素优先级”的接口，这是很多算法（如 Dijkstra）必须手写堆的原因
- 调试时可把内部
c成员（底层容器）用const_cast强转出来观察，但别修改——破坏堆序会导致后续操作未定义行为
小顶堆 vs 大顶堆：改一个参数还是重写两套逻辑
别重写。C++ 标准库靠比较器控制堆序：priority_queue 是小顶堆，less 是大顶堆。自己实现时也应统一用模板比较器，而不是硬编码 > 或 。
真正容易错的是：以为把所有 > 换成 就行——其实向上/向下调整中“违反堆序”的判定方向必须一致。例如小顶堆要求父 ≤ 子，那么 heapify_up 中就要写 if (heap[i] >= heap[parent]) break;，不是简单翻转符号。
- 把比较逻辑抽成独立函数对象或 lambda，传入调整函数
- 测试时务必用混杂正负数的用例，避免因全正/全负掩盖符号错误
- 注意
std::greater对自定义类型需重载operator>，而std::less需operator，别搞反
真实场景里，最常被忽略的是调整过程中对容器 size 的动态信任——比如在 heapify_down 里传入的 size 如果不是当前有效长度（例如删了元素但没 shrink），就会访问野指针；或者多线程环境下没加锁，size() 和后续下标访问之间被 resize 了。这些不会报编译错误，但 core dump 很安静。
