我正在寻找关于如何有效实现二叉堆的信息。我觉得应该有一篇很好的文章介绍如何高效地实现堆，但我还没有找到。事实上，除了将堆存储在数组中之类的基础知识外，我无法找到关于高效实现的任何资源。我正在寻找用于使二叉堆更快的技术，超出了我下面描述的技术。
我已经编写了一个C++实现，比Microsoft Visual C++和GCC的std::priority_queue或使用std::make_heap、std::push_heap和std::pop_heap更快。以下是我的实现中已经涵盖的技术。最后两个技术是我自己想出来的，尽管我怀疑这些都不是新思路：
（编辑：添加了关于内存优化的部分） 从1开始计数
查看二叉堆的 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少一点的比较。
相反，我们可以在堆中留下一个空洞，即顶部元素所在的位置。然后，我们通过迭代地将较大的子项向上移动来将该空洞向下移动到堆中。这只需要每个级别1次比较。这样，空洞将变成一个叶子。此时，我们可以将最右下角的叶子移到空洞的位置，并将该值向上移动，直到恢复堆属性。由于我们移动的值是叶子，我们不希望它在树上移动得太远。因此，我们应该预期比以前多一点的log n比较，这比以前更好。
Support replace-top： 假设您想要删除最大元素并插入一个新元素。然后，您可以执行上述任一删除/弹出实现之一，但是不使用右下角叶子节点，而是使用要插入/推入的新值。（当大多数操作都是这种类型时，我发现锦标赛树比堆更好，但否则堆略微更好。）
Make sizeof(T) a power of 2： 父亲、左孩子和右孩子的公式适用于索引，它们无法直接在指针值上工作。因此，我们将使用索引进行操作，这意味着在从索引i查找数组p中的值p[i]。如果p是T*，i是整数，则：
预先乘索引
在我的数据集上，这提高了23％的性能。除了查找父项，左子项和右子项之外，我们所做的唯一事情就是在数组中查找索引。因此，如果我们跟踪 j = sizeof（T）* i 而不是索引 i，则可以做一个查找 p[i]，而无需隐含在评估 p[i] 中的乘法操作。
如果sizeof(T)是2的幂，则此代码将编译为2个移位操作。这比使用索引i的通常父节点多1个操作。但是，我们可以节省1个查找操作。因此，以这种方式查找父节点需要相同的时间，而查找左右子节点的速度更快。
内存优化：TokenMacGuy和templatetypedef的答案指出了基于内存的优化，可减少缓存未命中率。对于非常大的数据集或不经常使用的优先队列，操作系统可以将队列的部分交换到磁盘上。在这种情况下，值得添加很多开销来最大限度地利用缓存，因为从磁盘中交换的速度非常慢。我的数据轻松适合内存并且持续使用，因此队列的任何部分都不太可能被交换到磁盘上。我怀疑这是大多数优先队列使用情况的情况。问题
除了这些技术，还有其他技术吗？
我已经编写了一个C++实现，比Microsoft Visual C++和GCC的std::priority_queue或使用std::make_heap、std::push_heap和std::pop_heap更快。以下是我的实现中已经涵盖的技术。最后两个技术是我自己想出来的，尽管我怀疑这些都不是新思路：
（编辑：添加了关于内存优化的部分） 从1开始计数
查看二叉堆的 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少一点的比较。
相反，我们可以在堆中留下一个空洞，即顶部元素所在的位置。然后，我们通过迭代地将较大的子项向上移动来将该空洞向下移动到堆中。这只需要每个级别1次比较。这样，空洞将变成一个叶子。此时，我们可以将最右下角的叶子移到空洞的位置，并将该值向上移动，直到恢复堆属性。由于我们移动的值是叶子，我们不希望它在树上移动得太远。因此，我们应该预期比以前多一点的log n比较，这比以前更好。
Support replace-top： 假设您想要删除最大元素并插入一个新元素。然后，您可以执行上述任一删除/弹出实现之一，但是不使用右下角叶子节点，而是使用要插入/推入的新值。（当大多数操作都是这种类型时，我发现锦标赛树比堆更好，但否则堆略微更好。）
Make sizeof(T) a power of 2： 父亲、左孩子和右孩子的公式适用于索引，它们无法直接在指针值上工作。因此，我们将使用索引进行操作，这意味着在从索引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的答案指出了基于内存的优化，可减少缓存未命中率。对于非常大的数据集或不经常使用的优先队列，操作系统可以将队列的部分交换到磁盘上。在这种情况下，值得添加很多开销来最大限度地利用缓存，因为从磁盘中交换的速度非常慢。我的数据轻松适合内存并且持续使用，因此队列的任何部分都不太可能被交换到磁盘上。我怀疑这是大多数优先队列使用情况的情况。
有其他优先队列的设计旨在更好地利用CPU缓存。例如，4-堆应该有较少的缓存未命中，额外开销也不是很大。LaMarca和Ladner在1996年报告称，他们通过采用对齐的4-堆获得了75％的性能提升。然而，Hendriks在2010年报告说：
为了改善数据局部性并减少缓存未命中，LaMarca和Ladner建议对隐式堆进行改进[17]。我们实现了一个四路堆，在非常倾斜的输入数据情况下确实显示出比二路堆略微更好的一致性，但仅适用于非常大的队列大小。非常大的队列大小最好由分层堆处理。
除了这些技术，还有其他技术吗？
a创建指向a[-1]的指针在技术上也是非法的。它可能在您的编译器上工作 - 甚至可能在所有编译器上都能工作，或多或少 - 但从技术上讲是不允许的。只是提供信息。 - Nemo