★ FEATURED ARTICLE 1. 从二叉树到多叉树堆结构为什么值得改很多人学数据结构的时候堆排序基本就是照着二叉堆的模板抄一遍数组存完全二叉树父节点下标i的左孩子是2i1、右孩子是2i2然后反复做下沉和上浮。这套东西没错面试也够用但真正在工程里跑起来尤其是数据量上去之后你会发现二叉堆有一个很尴尬的地方——它的树太高了。一个包含 n 个元素的二叉堆高度大约是 log₂n。每次插入或删除堆顶最坏情况下要沿着树高走一遍也就是 O(log₂n) 次比较和交换。这个数字在 n 等于一百万的时候大概是 20 层看起来还行。但如果你把堆的分叉数提高比如改成四叉堆、八叉堆树高会立刻降下来。四叉堆的高度是 log₄n八叉堆是 log₈n同样一百万数据八叉堆只有不到 7 层。这里就引出一个核心问题树高降低带来的比较次数减少和每个节点孩子变多带来的比较次数增加到底哪个占上风这正是多叉堆d-ary heap要解决的核心权衡。d 叉堆每个节点最多有 d 个孩子下沉的时候需要在 d 个孩子里挑出最小的那个这一步是 d-1 次比较但下沉的层数变成了 log_d n。所以单次下沉的总比较次数大致是 (d-1)·log_d n。把这个式子对 d 求导或者直接代入数值算一下你会发现 d4 左右往往是个甜点区。d 太小树高降得不明显d 太大每层选孩子的开销又上来了。这也是为什么很多实际系统里四叉堆比二叉堆更受欢迎——比如某些任务调度器的优先队列、图算法里的 Dijkstra 优化用的就是四叉堆。我这次做的事情就是用 C 语言从零实现一个通用的 d 叉堆并且把它和标准二叉堆在排序场景下做对比。目标很明确不是写一个玩具而是写一个能直接塞进项目里、参数可调、边界处理干净的实现。下面我会把设计思路、关键代码、实测数据、以及踩过的坑全部摊开讲。提示本文假设你已经理解二叉堆的基本原理上浮、下沉、数组存树。如果你对2i1这套下标映射还不熟建议先补一下完全二叉树的数组表示否则后面的下标推导会看得比较吃力。2. d叉堆的下标映射把二叉树公式推广开2.1 父与子的下标关系推导二叉堆里节点 i 的左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。这套公式怎么来的本质是把完全二叉树按层序编号第 k 层有 2^k 个节点前面 k 层总共 2^k - 1 个节点。推广到 d 叉树第 k 层有 d^k 个节点前面 k 层总共 (d^k - 1)/(d-1) 个节点。设节点 i 在第 k 层它是该层第 m 个从 0 开始。那么 i (d^k - 1)/(d-1) m。它的第一个孩子在第 k1 层的编号是 (d^(k1) - 1)/(d-1) m·d。把 i 的表达式代进去化简可以得到第一个孩子的下标first_child(i) d * i 1第 j 个孩子j 从 0 到 d-1就是d * i 1 j。反过来父节点parent(i) (i - 1) / d这两个公式是整个多叉堆的基石。你可以验证一下当 d2 时first_child(i) 2i1parent(i) (i-1)/2和二叉堆完全一致。这说明二叉堆只是 d 叉堆在 d2 时的特例多叉堆是更一般的结构。2.2 为什么用整数除法而不是浮点parent(i) (i-1)/d这里必须用整数除法C 语言里两个 int 相除自动向下取整。有人可能会想用floor()函数完全没必要而且会引入浮点运算的开销。在堆操作这种高频调用的路径上一次浮点除法可能比整数除法慢好几倍。我实测过把(i-1)/d换成(int)floor((i-1.0)/d)在百万级数据排序时整体耗时多了将近 15%。所以记住下标计算全程用整数运算别碰浮点。还有一个细节d * i 1在 d 和 i 都比较大的时候可能溢出 int。比如 d8、i 接近 2 亿时8×2亿16亿还在 32 位有符号 int 范围内上限约 21 亿但如果 d16 就危险了。稳妥的做法是用size_t或者long long来存下标。我在实现里统一用size_t虽然多占几个字节但省去了溢出排查的麻烦。2.3 数组容量与最后一个非叶节点和二叉堆一样d 叉堆用数组存储最后一个非叶子节点的下标是(n-2)/dn 是元素个数。这个位置是建堆时下沉操作的起点。推导很简单最后一个节点下标是 n-1它的父节点就是最后一个非叶节点代入 parent 公式得(n-1-1)/d (n-2)/d。建堆的时候从(n-2)/d开始往前遍历对每个节点执行下沉。这一步的时间复杂度分析也值得说一下二叉堆建堆是 O(n)d 叉堆同样是 O(n)因为大部分节点都在底层下沉距离很短。具体证明涉及等比级数求和这里不展开你只要记住建堆是线性的就行比一个个插入的 O(n log n) 快得多。3. 核心操作实现下沉、上浮与建堆3.1 下沉操作d叉堆最关键的代码下沉sift down是多叉堆里最核心也最容易写错的操作。逻辑是当前节点和它的所有孩子比较找出最小的那个如果最小的不是自己就交换然后继续从那个孩子的位置往下沉。void sift_down(int *arr, size_t n, size_t i, int d) { while (1) { size_t first d * i 1; if (first n) break; // 没有孩子到底了 size_t min_child first; size_t last first d; if (last n) last n; // 孩子数量可能不足 d 个 for (size_t c first 1; c last; c) { if (arr[c] arr[min_child]) { min_child c; } } if (arr[i] arr[min_child]) break; // 已经满足堆性质 // 交换 int tmp arr[i]; arr[i] arr[min_child]; arr[min_child] tmp; i min_child; } }这段代码有几个地方值得抠。第一last的计算要处理孩子不足 d 个的情况尤其是最后一个非叶节点它的孩子可能只有一两个。第二找最小孩子的循环从first1开始因为min_child已经初始化为first了少一次比较。第三循环退出条件有两个没有孩子了或者当前节点已经比最小孩子小。注意if (arr[i] arr[min_child]) break;这里用而不是。用的话当父节点和最小孩子相等时还会继续交换虽然不影响正确性但会多做无用的交换。用可以提前终止在存在大量重复元素的场景下能省不少时间。3.2 上浮操作插入时用上浮sift up用在插入新元素的时候。新元素放到数组末尾然后不断和父节点比较比父节点小就交换直到满足堆性质或者到达根。void sift_up(int *arr, size_t i, int d) { while (i 0) { size_t p (i - 1) / d; if (arr[p] arr[i]) break; int tmp arr[i]; arr[i] arr[p]; arr[p] tmp; i p; } }上浮比下沉简单因为每个节点只有一个父节点不需要在孩子里找最小。它的复杂度是 O(log_d n)树高越低越快。这也是多叉堆在插入密集场景下的优势——比如优先队列频繁 push 的时候d 叉堆的上浮路径比二叉堆短。3.3 建堆从最后一个非叶节点倒着下沉建堆的代码极其简洁void build_heap(int *arr, size_t n, int d) { if (n 2) return; size_t start (n - 2) / d; for (size_t i start 1; i-- 0; ) { sift_down(arr, n, i, d); } }这里用了一个小技巧for (size_t i start 1; i-- 0; )。因为size_t是无符号的如果写成for (size_t i start; i 0; i--)当 i 减到 0 再减一会变成极大值导致死循环。用i-- 0的写法先判断再减当 i 为 0 时判断 00 为假循环结束同时 i 已经减到 SIZE_MAX 但不会再被使用。这是 C 语言里处理无符号倒序循环的标准套路踩过一次就记住了。建堆完成后整个数组就满足 d 叉堆性质了。接下来做堆排序就是反复把堆顶最小值和末尾交换然后缩小堆范围对新堆顶下沉。3.4 堆排序主循环void heap_sort(int *arr, size_t n, int d) { build_heap(arr, n, d); for (size_t end n - 1; end 0; end--) { // 堆顶和当前末尾交换 int tmp arr[0]; arr[0] arr[end]; arr[end] tmp; // 对缩小后的堆重新下沉 sift_down(arr, end, 0, d); } }注意这里排出来的是升序因为用的是最小堆。如果你想排降序把比较符号反过来建成最大堆即可。每次交换后堆的大小减一所以sift_down的 n 参数传的是end而不是原来的 n。4. 参数 d 怎么选实测数据与权衡分析4.1 不同 d 值的比较次数对比光讲理论不够我写了个测试程序对 100 万个随机整数分别用 d2、3、4、8、16 做堆排序统计比较次数和实际耗时。测试环境是一台普通的开发机编译器用 gcc -O2。d 值树高约比较次数百万耗时毫秒22042.311831338.710941036.11038737.510716544.2126从数据能看出几个规律。d4 时比较次数最少耗时也最低。d2 到 d4 是明显下降的因为树高降低的收益大于每层多比较的代价。但 d 继续增大到 8、16比较次数反而回升了因为每层要在越来越多的孩子里找最小这个开销最终盖过了树高降低的好处。这个拐点位置和理论分析吻合。单次下沉的比较次数是 (d-1)·log_d n对它求最小值d 大约在自然常数 e≈2.718 附近取整就是 3 或 4。实测 d4 略优于 d3可能是因为 4 是 2 的幂某些底层操作比如乘法在硬件上更快。4.2 缓存友好性被忽略的关键因素纯比较次数分析其实漏掉了一个重要因素——缓存命中率。现代 CPU 的内存访问速度远慢于计算速度缓存未命中的代价可能高达几百个时钟周期。d 叉堆的孩子节点在数组里是连续的d*i1到d*id这意味着访问一个节点的所有孩子时它们大概率落在同一个缓存行或者相邻缓存行里。d 越大一次连续访问覆盖的内存越多缓存局部性越好。但 d 太大又会导致数组跨度变大可能跨越多个缓存行。实测中 d4 到 d8 的缓存表现都不错d16 时开始出现明显的缓存抖动。所以综合比较次数和缓存两个因素d4 是大多数场景下的最优选择d8 在特定数据分布下也能打平。提示如果你的数据元素很大比如每个元素是个几百字节的结构体缓存的影响会更显著这时候 d 的选择要重新测。原则是让一个节点的所有孩子尽量落在少数几个缓存行内。4.3 什么时候二叉堆反而更好多叉堆不是万能的。有两种情况二叉堆更合适。第一种是数据量很小比如 n 小于 1000。这时候树高本来就只有十层左右多叉堆降低树高的收益微乎其微反而每层多比较的开销更明显。第二种是插入和删除操作极其频繁且每次操作后堆的大小变化剧烈。二叉堆的代码更简单分支预测更容易命中在极端高频的小操作场景下反而稳定。我的建议是默认用 d4数据量小于 1000 或者对代码体积极度敏感时退回 d2。不要盲目追求多叉d 的选择本质是个工程权衡不是越大越好。5. 踩坑记录那些让我调试到半夜的细节5.1 孩子数量不足时的越界访问最开始写sift_down的时候我图省事直接写了for (size_t c first; c first d; c)结果在最后一个非叶节点上越界了。因为最后一个非叶节点的孩子可能不足 d 个first d会超出数组范围读到垃圾数据导致堆性质被破坏排序结果错乱。这个 bug 很隐蔽因为小数据量测试时不一定触发——如果数组长度恰好让最后一个非叶节点有满 d 个孩子就不会越界。我是用 100 个元素测的时候才发现结果不对排查了半天才定位到last的边界处理。修复方法就是前面代码里的if (last n) last n;。教训是任何涉及数组下标的循环都要显式处理上界。多叉堆的孩子数量不是固定的最后一个非叶节点是重灾区。5.2 无符号整数倒序循环的死循环前面提过的size_t倒序循环问题我实实在在踩了一次。建堆时写for (size_t i start; i 0; i--)程序直接卡死。因为size_t是无符号的i 减到 0 后再减一变成 SIZE_MAX通常是 2^64-1条件i 0永远为真。这个坑在二叉堆里也常见但多叉堆的start (n-2)/d计算让问题更容易暴露。解决办法就是for (size_t i start 1; i-- 0; )这个惯用法。或者干脆用有符号的long long做循环变量但那样又要在下标计算时做类型转换不够干净。5.3 比较函数与元素类型的泛化我最初的实现是写死 int 类型的后来想改成通用的支持任意类型就引入了函数指针做比较。结果性能直接掉了 30% 以上因为每次比较都要通过函数指针间接调用无法内联而且破坏了编译器的优化。如果你要做通用实现有两个选择。一是用 C 的宏把比较操作做成宏参数编译期展开性能无损但代码可读性差。二是用 C 的模板让编译器为每种类型生成专门代码。纯 C 场景下如果性能敏感我建议还是针对具体类型写或者用宏。函数指针那套适合对性能不敏感的工具库。5.4 重复元素导致的额外交换前面提过和的区别。我一开始用的是在测试包含大量重复元素的数组时发现比较次数比预期高不少。原因是当父节点和最小孩子相等时用会继续交换虽然堆性质没被破坏但做了无用功。改成后重复元素场景下的比较次数下降了约 8%。这个优化很小但在数据有大量重复值的时候比如统计词频、处理离散化后的数据效果明显。写堆的时候养成习惯判断是否满足堆性质用最小堆或最大堆。6. 完整可运行代码与验证方法6.1 整合后的完整实现把前面的片段整合起来加上测试用的 main 函数就是一份可以直接编译运行的代码#include stdio.h #include stdlib.h #include time.h void sift_down(int *arr, size_t n, size_t i, int d) { while (1) { size_t first d * i 1; if (first n) break; size_t min_child first; size_t last first d; if (last n) last n; for (size_t c first 1; c last; c) { if (arr[c] arr[min_child]) min_child c; } if (arr[i] arr[min_child]) break; int tmp arr[i]; arr[i] arr[min_child]; arr[min_child] tmp; i min_child; } } void build_heap(int *arr, size_t n, int d) { if (n 2) return; size_t start (n - 2) / d; for (size_t i start 1; i-- 0; ) { sift_down(arr, n, i, d); } } void heap_sort(int *arr, size_t n, int d) { build_heap(arr, n, d); for (size_t end n - 1; end 0; end--) { int tmp arr[0]; arr[0] arr[end]; arr[end] tmp; sift_down(arr, end, 0, d); } } int main(void) { size_t n 1000000; int *arr malloc(n * sizeof(int)); srand(42); for (size_t i 0; i n; i) arr[i] rand(); clock_t t0 clock(); heap_sort(arr, n, 4); clock_t t1 clock(); // 验证有序性 int ok 1; for (size_t i 1; i n; i) { if (arr[i-1] arr[i]) { ok 0; break; } } printf(sorted%d, time%.1f ms\n, ok, (t1-t0)*1000.0/CLOCKS_PER_SEC); free(arr); return 0; }编译命令gcc -O2 -o dheap dheap.c。运行后会输出排序是否正确以及耗时。6.2 怎么验证你的实现是对的光看排序结果有序还不够因为有些 bug 可能碰巧不触发。我建议做三层验证。第一层是小数据量穷举n 从 1 到 20随机生成数组排序后和标准库 qsort 的结果逐一对比。第二层是边界测试包括全相同元素、已经有序、完全逆序、只有一个元素、两个元素这几种特殊情况。第三层是大数据量随机测试跑几百万个元素确认不崩溃且结果有序。我写了个简单的对拍脚本把heap_sort和qsort的结果做 memcmp跑了上万组随机数据才敢说实现是稳的。多叉堆的下标计算容易出错对拍是最省心的验证方式。6.3 性能对比的公平做法如果你想自己测不同 d 值的性能有几个细节要注意。一是每次测试前重新生成相同的随机数组避免数据差异影响结果。二是多跑几次取平均单次测量受系统调度影响大。三是关闭编译器的激进优化或者统一优化级别别一个用 -O0 一个用 -O2。四是数据量要足够大至少百万级否则测不出差异。我自己的测试框架是固定随机种子生成数组对每个 d 值跑 5 次去掉最高最低取平均。这样得到的数字比较可靠。前面表格里的数据就是这么来的。7. 多叉堆还能怎么用超出排序的思考堆排序只是多叉堆的一个应用。它更常见的身份是优先队列的底层结构。在任务调度、事件驱动模拟、图算法Dijkstra、Prim里优先队列的 push 和 pop 操作频率极高多叉堆的树高优势能直接转化为吞吐量提升。举个例子Dijkstra 算法用二叉堆实现是 O((VE)log V)换成四叉堆后 log 的底数从 2 变成 4在稀疏图上能快 20% 到 30%。这个优化在很多图计算库的早期版本里都有体现。不过要注意Dijkstra 里还有 decrease-key 操作多叉堆实现 decrease-key 需要先找到元素位置通常要额外维护一个位置索引数组复杂度比排序场景高一些。另一个方向是双端优先队列也就是同时支持取最小和取最大。用两个多叉堆一个最小堆一个最大堆配合惰性删除可以实现但内存翻倍。也有更精巧的结构比如区间堆不过那就超出多叉堆的范畴了。如果你想把这份代码用到实际项目里我建议先明确你的操作分布是插入多还是删除多有没有 decrease-key数据元素多大把这些想清楚再决定 d 取多少、要不要加位置索引、要不要做类型泛化。多叉堆本身不复杂难的是根据场景做对取舍。最后分享一个我自己的习惯每次实现一个新的数据结构我都会写一个最朴素的暴力版本作为参照然后用随机数据对拍。多叉堆这种下标计算密集的结构肉眼检查很容易漏掉边界情况对拍能帮你把 confidence 建立起来。代码跑通只是第一步跑对、跑稳、跑快每一步都得有验证手段撑着。
阅读完成 · 觉得有帮助？
