二叉堆能用一维数组存储,因为完全二叉树层序编号下父子节点下标存在确定关系:根在0时,左子为2i+1、右子为2i+2、父为(i−1)/2(整除),无需指针即可通过下标快速定位,实现紧凑、高效、无碎片的顺序存储。

二叉堆为什么能用一维数组存
因为完全二叉树的节点编号有确定规律:若根节点下标为 0,则任意节点 i 的左子节点在 2*i + 1,右子节点在 2*i + 2,父节点在 (i - 1) / 2(整除)。只要按层序遍历顺序把节点填进数组,就能靠下标算出父子关系,根本不需要指针或结构体嵌套。
插入新元素时怎么上浮(sift up)
新元素总加在数组末尾,然后和父节点比较:如果比父小(小顶堆)就交换,重复直到满足堆序。关键点是下标更新必须及时,且边界检查不能漏掉根节点(i == 0 时停止)。
常见错误:
- 用
i / 2算父节点——这是下标从 1 开始的写法,C++ 数组通常从 0 开始,得用(i - 1) / 2 - 循环条件写成
i > 0 && arr[i] ——这里i/2错了,而且没括号,整除逻辑混乱 - 交换后忘了更新
i,导致死循环
正确片段示意:
void push(int val) {
heap.push_back(val);
int i = heap.size() - 1;
while (i > 0) {
int p = (i - 1) / 2;
if (heap[i] >= heap[p]) break;
std::swap(heap[i], heap[p]);
i = p;
}
}
弹出堆顶时怎么下沉(sift down)
把最后一个元素移到堆顶,然后和两个子节点中较小的那个比较、交换,重复直到它比两个子都小或已无子节点。注意:必须先确认子节点存在(left ),再取值比较;否则越界访问。
容易踩的坑:
- 只和左子比较,忽略右子更小的可能
- 用
2*i和2*i+1当子节点下标——这又默认了下标从 1 开始 - 下沉过程中,交换后没更新当前下标
i,导致逻辑卡住 - 没处理“只有一个子节点”的情况(右子可能越界)
关键判断逻辑应类似:
std::make_heap
C++免费学习笔记(深入):立即使用
在学习笔记中,你将探索 C++ 的入门与实战技巧!











