堆在真实系统里的形态

前四页的堆都持有 key 的副本，push(k) 之后那个数值就归堆管。真实系统里几乎没有这种堆：入队的是一个连接、一个定时器、一个待办任务，堆只负责给它们排序，对象的生命周期归别人管。

这一条差别改写了实现的每一层：节点存在哪里、删除怎么做、以及这个负载到底该不该用堆。

1 · 节点内嵌进业务对象

libuv 的 src/heap-inl.h 是这种写法的标准样本（v1.x 分支，245 行，核对于 2026-08）。它的节点定义里没有 key：

struct heap_node {
  struct heap_node* left;
  struct heap_node* right;
  struct heap_node* parent;
};

struct heap {
  struct heap_node* min;
  unsigned int nelts;
};

业务对象把 heap_node 当作一个字段嵌在自己里面，比较交给调用方传入的 heap_compare_fn：它拿到两个 heap_node*，用 container_of 回推到外层对象再读 key。这样的堆只有两个字段，且不分配任何内存——heap_insert 收到的节点从头到尾归调用方持有。这就是侵入式堆。

它有一个不容易一眼看出的推论：侵入式堆不可能是数组堆。数组堆的存储属于数组自己，元素进去就要复制、排序时还要移动，而侵入式的前提恰恰是对象原地不动。libuv 把完全二叉树用 parent、left、right 三根指针显式建了出来。

随之而来的问题是「底层最左的空位」怎么找。数组堆里它就是下标 nelts，指针树里没有下标。libuv 的答案是把 1 + nelts 逐位右移，把每一位压进一条路径，再按位走左或走右：

path = 0;
for (k = 0, n = 1 + heap->nelts; n >= 2; k += 1, n /= 2)
  path = (path << 1) | (n & 1);

这是下标算术的指针版本。完全二叉树里从根到第 $i$ 个节点的路径本来就写在 $i$ 的二进制位里，数组堆用除法读它，指针树用移位读它。

代价落在交换上。数组堆交换两个元素是写两个格子；heap_node_swap 要换掉两个结构体的内容，再修正双方的父亲、四个孩子、以及被换下来那个节点的兄弟，一次交换动到五六处指针。

2 · 任意删除的前提

「把某个已入队的对象撤掉」在真实系统里是常规需求：连接断了要撤掉它的超时，任务取消了要撤掉它的调度。这个操作的复杂度只取决于一件事：能不能不搜索就知道这个对象在哪，与堆的形状无关。

libuv 的答案是节点本身就是位置：heap_remove(heap, node, less_than) 收到的就是那根指针。数组堆的对应做法是在对象里存一个下标字段，每次交换时同步更新，与 索引堆与 decrease-key §2 的 pos 数组同构。

没有这份信息就只能扫描。1000 个节点里删掉 200 个的实测：带位置字段时删除动作本身做 556 次比较、1696 次写入；不带时，光是定位就要扫过 102764 格，平均每次 514 格。删除的 $O(\log n)$ 被定位的 $O(n)$ 完全淹没。

heap_remove 里还有一处值得抄下来的细节：把最后一个节点填进空位之后，它先下沉再上浮，两步都做。源码注释给了理由，填进来的那个节点不保证是子树里最大的，它可能反而需要往上走。本页引擎里的实现顺序相反（先上浮，没动才下沉），效果相同，但两步都不能省。

3 · 墓碑与延迟清理

Go runtime 走的是另一条路。runtime/time.go 里每个 P 一套定时器，底层是数组式的 4 叉堆（const timerHeapN = 4），数组元素是 timerWhen{timer *timer; when int64}：一根指针加一份 when 的副本，下沉比较时不必解引用去读对象。

timer 结构里有 ts *timers 记着自己在哪个 P 的堆里，却没有下标字段。于是 t.stop() 没法把它摘掉，源码注释把理由说得很直接：

It may be on some other P, so we can't actually remove it from the timers heap. We can only mark it as stopped. It will be removed in due course by the P whose heap it is on.

stop 做的是置一个 timerZombie 位、给该 P 的 zombies 计数加一。真正的清除推给拥有这个堆的 P，在 cleanHead 里做，并且优先从堆尾摘僵尸条目——那里的注释写着，这样做「完全不需要调整堆」。

这就是墓碑在堆上的形态：删除变成打标记，代价推后到出堆时丢弃。它的吸引力不在性能，而在不必跨线程去动别人的数据结构。约束条件不是复杂度，是并发模型。

4 · 定时器负载与时间轮

20000 个定时器、延时上界 256 个 tick 的实测。取消 50% 时立即摘除做 184413 次比较，墓碑做 267686 次；取消 90% 时是 144538 对 268414。

其中最值得记下的一条：墓碑写法的比较次数与取消比例几乎无关。取消比例从 10% 排到 90%，五档的比较次数分别是 268873、268407、267686、267964、268414，全程波动不到 0.5%。被取消的条目并没有离开堆，它照样参与此后每一次下沉比较，直到轮到它出堆才被丢弃。立即摘除那一栏则从 247268 一路降到 144538：取消得越多，堆越小，后面越省。

第三栏换掉了整个结构。时间轮按到期时刻取模落槽，添加与取消各是一次链表操作，处理到期只看当前槽，全程一次 key 比较都不做，写入次数在三成上下。定时器负载常常绕开堆，理由就是这一栏：这类负载里绝大多数定时器等不到触发就被取消，而堆为「取出最小」付的那份 $\log n$ 换不到对应的收益。结构本身见 时间轮 Timing Wheel。

时间轮的代价同样明确：延时必须落在窗口内，超出窗口要靠 rounds 计数或分层降级补，而这两种补法都会让「取消是 $O(1)$」这条性质变得有条件。libuv 与 Go 都选了堆而不是时间轮，因为它们要支持任意长的超时，且单个事件循环里的定时器数量通常只有几百个——那个规模上 $\log n$ 不到十次比较，换结构不值。

5 · 参考文献

1. Noordhuis, B. (2013–). libuv src/heap-inl.h [源码]. https://github.com/libuv/libuv/blob/v1.x/src/heap-inl.h
2. The Go Authors. Go runtime src/runtime/time.go [源码]. https://github.com/golang/go/blob/master/src/runtime/time.go
3. Varghese, G., & Lauck, T. (1987). Hashed and hierarchical timing wheels: Data structures for the efficient implementation of a timer facility. ACM SIGOPS Operating Systems Review, 21(5), 25–38.