我正在寻找有关如何实现的信息 binary heaps有效率的。我觉得应该有一篇关于有效实现堆的不错的文章，但我还没有找到。事实上，除了将堆存储在数组中等基础知识之外，我一直无法找到有关有效实现问题的任何资源。我正在寻找制作快速二进制堆的技术，而不是我在下面描述的那些。
我已经编写了比 Microsoft Visual C++ 和 GCC 的 std::priority_queue 或使用 std::make_heap、std::push_heap 和 std::pop_heap 更快的 C++ 实现。以下是我在实现中已经涵盖的技术。我自己只想到了最后两个，尽管我怀疑这些是新想法:
(编辑:添加了关于内存优化的部分)
看Wikipedia implementation notes对于二进制堆。如果堆的根位于索引 0 处，则索引 n 处节点的父节点、左子节点和右子节点的公式分别为 (n-1)/2、2n+1 和 2n+2。如果您使用基于 1 的数组，则公式将变为更简单的 n/2、2n 和 2n + 1。因此，使用基于 1 的数组时，父级和左子级的效率更高。如果 p 指向一个基于 0 的数组并且 q = p - 1 那么我们可以将 p[0] 作为 q[1] 访问，因此使用基于 1 的数组没有开销。
堆上的弹出经常被描述为用最左边的底部叶子替换顶部元素，然后将其向下移动，直到恢复堆属性。这需要我们经过的每个级别进行 2 次比较，并且由于我们将叶子移动到堆的顶部，因此我们可能会在堆中走得很远。所以我们应该期望少于 2 log n 的比较。
相反，我们可以在顶部元素所在的堆中留下一个洞。然后我们通过迭代向上移动较大的 child 来将这个洞向下移动。这仅需要我们经过的每个级别进行 1 次比较。这样，洞就会变成一片叶子。在这一点上，我们可以将最右边的底部叶子移动到孔的位置并向上移动该值，直到恢复堆属性。由于我们移动的值是一片叶子，我们不希望它在树上移动很远。所以我们应该期待比 log n 多一点的比较，这比以前更好。
假设您要删除 max 元素并插入一个新元素。然后您可以执行上述任何一个删除/弹出实现，但不是移动最右侧的底部叶子，而是使用您希望插入/推送的新值。 (当大多数操作都属于这种类型时，我发现锦标赛树比堆好，但除此之外，堆稍微好一些。)
父、左子和右子公式适用于索引，不能直接作用于指针值。所以我们将使用索引，这意味着从索引 i 查找数组 p 中的值 p[i]。如果 p 是 T* 且 i 是整数，则
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i
并且编译器必须执行此计算才能获得 p[i]。 sizeof(T) 是编译时常量，如果 sizeof(T) 是 2 的幂，则乘法可以更有效地完成。通过添加 8 个填充字节将 sizeof(T) 从 24 增加到 32，我的实现变得更快。缓存效率的降低可能意味着这对于足够大的数据集来说不是一个胜利。
这使我的数据集的性能提高了 23%。除了查找父、左子和右子之外，我们对索引所做的唯一一件事就是在数组中查找索引。因此，如果我们跟踪 j = sizeof(T) * i 而不是索引 i，那么我们可以在没有乘法的情况下进行查找 p[i]，否则在评估 p[i] 时是隐含的，因为
&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j
然后 j 值的左子和右子公式分别变为 2*j 和 2*j + sizeof(T)。父公式有点棘手，除了将 j 值转换为 i 值并返回如下之外，我还没有找到其他方法:
parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)
如果 sizeof(T) 是 2 的幂，那么这将编译为 2 个类次。这比使用索引 i 的通常父级多 1 个操作。但是，我们然后在查找时保存 1 个操作。因此，最终的结果是，以这种方式查找父项花费的时间相同，而查找左子项和右子项的速度会更快。
TokenMacGuy 和 templatetypedef 的答案指出了基于内存的优化，可以减少缓存未命中。对于非常大的数据集或不常使用的优先级队列，OS 可以将部分队列换出到磁盘。在这种情况下，增加大量开销以优化使用缓存是值得的，因为从磁盘换入非常慢。我的数据很容易放在内存中并持续使用，所以队列的任何部分都不会被交换到磁盘。我怀疑这是优先级队列的大多数用途的情况。
还有其他优先级队列旨在更好地利用 CPU 缓存。例如，一个 4 堆应该有更少的缓存未命中，额外的开销不会那么多。 LaMarca and Ladner 1996 年的报告称，通过使用对齐的 4 堆，他们获得了 75% 的性能提升。然而，Hendriks 2010 年的报告指出:
The improvements to the implicit heap suggested by LaMarca and Ladner [17] to improve data locality and reduce cache misses were also tested. We implemented a four-way heap, that indeed shows a slightly better consistency than the two-way heap for very skewed input data, but only for very large queue sizes. Very large queue sizes are better handled by the hierarchical heap.
还有比这些更多的技术吗？
最佳答案
关于这个主题的一篇有趣的论文/文章考虑了堆整体布局上的缓存/分页行为；这个想法是，与数据结构实现的几乎任何其他部分相比，为缓存未命中或页面支付的成本要高得多。本文讨论了解决此问题的堆布局。
You're Doing It Wrong
by Poul-Henning Kamp
关于c++ - 二叉堆的高效实现，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/6531543/