高效实现二进制堆 [英] Efficient implementation of binary heaps

问题描述

我正在寻找有关如何有效实施二进制堆的信息。我觉得应该有一个很好的文章，有效地实现堆，但我还没有找到一个。事实上，我已经无法找到任何有关高效实现的资源，除了基本知识之外，例如将堆存储在数组中。我正在寻找一个快速二进制堆超越下面描述的技术。

我已经写了一个比Microsoft Visual C ++更快的C ++实现， GCC的std :: priority_queue或使用std :: make_heap，std :: push_heap和std :: pop_heap。以下是我已经在我的实现中涵盖的技术。我只想出了最后2个自己，虽然我怀疑那些是新的想法：

（编辑：内存优化的添加部分）

在1处开始索引

查看 Wikipedia implementation notes for binary heaps。如果堆的根位于索引0处，则索引n处的节点的父节点，左孩子和右孩子的公式分别为（n-1）/ 2,2n + 1和2n + 2。如果使用基于1的数组，那么公式变成更简单的n / 2,2n和2n + 1.因此，当使用基于1的数组时，parent和left-child更有效。如果p指向一个基于0的数组并且q = p - 1，那么我们可以访问p [0]作为q [1]，所以在使用基于1的数组没有开销。

在用叶子替换之前，将弹出/移除元素移动到堆的底部

通常，最左边的叶子，然后将其向下移动，直到堆属性恢复。这需要每个级别的2个比较，我们可能会走到堆下，因为我们将一个叶子移动到堆的顶部。因此，我们应该期望一个小于2 log n的比较。

相反，我们可以在堆中留下一个洞，顶部元素是。然后我们通过迭代地移动更大的孩子向上移动那个洞在堆下。这只需要我们经过的每个级别的一个比较。这样，洞就会变成叶子。此时，我们可以将最右边的叶子移动到孔的位置，并向上移动该值直到堆属性被恢复。因为我们移动的值是一个叶子，我们不期望它移动非常远的树。

支持替换顶部

假设要删除max元素并插入一个新元素。然后，您可以执行上述的remove / pop实现，但是不是移动最右边的叶子，而是使用您希望插入/推送的新值。 （当大多数操作都是这种类型时，我发现比赛树比堆好，否则堆会更好。）

< b>使sizeof（T）为2的乘方

父，左子和右子公式适用于索引，它们不能直接用于指针值。因此，我们将使用索引，这意味着从索引i查找数组p中的值p [i]。如果p是T *并且i是整数，则

 &（p [i]）== static_cast < *>（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 $ b  

如果sizeof（T）是2的幂，那么这将编译为2个班次。比通常的父使用索引i。然而，我们然后保存1操作对查找。因此，净效果是，查找父亲需要相同的时间这种方式，而查找左孩子和右孩子变得更快。 p>

内存优化

TokenMacGuy和templatetypedef的答案指出基于内存优化，减少缓存缺失对于非常大的数据集或不经常使用的优先级队列，部分队列可以被操作系统交换到磁盘，在这种情况下，值得添加大量开销，以最佳利用因为从磁盘交换非常慢。我的数据很容易适合内存，并且是连续使用的，所以没有一部分队列可能会被交换到磁盘。我怀疑这是大多数使用优先级队列的情况。

还有其他优先级队列，旨在更好地利用CPU缓存。例如，4堆应该有更少的高速缓存未命中，额外的开销量不是那么多。 LaMarca和Ladner 报告在1996年，他们获得75％的性能提升去对齐4堆。不过，在2010年 Hendriks 报告：

还测试了LaMarca和Ladner提出的改进数据局部性和减少高速缓存未命中的隐含堆的改进。我们实现了一个四路堆，对于非常歪斜的输入数据，确实显示出比双向堆稍好的一致性，但只有非常大的队列大小。非常大的队列大小更适合处理分层堆。

问题

有比这些技术更多的技术吗？

解决方案

关于这个主题的一篇有趣的文章/文章考虑缓存/对堆的整体布局;这个想法是，比数据结构实现的几乎任何其他部分支付高速缓存未命中或页面花费更大的代价。本文讨论了解决此问题的堆布局。

您're Doing It Wrong
by Poul-Henning Kamp

I'm looking for information on how to implement binary heaps efficiently. I feel like there should be a nice article somewhere about implementing heaps efficiently, but I haven't found one. In fact I've been unable to find any resources on the matter of efficient implementation beyond the basics like storing the heap in an array. I'm looking for techniques for making a fast binary heap beyond the ones I describe below.

I've already written a C++ implementation that is faster than Microsoft Visual C++'s and GCC's std::priority_queue or using std::make_heap, std::push_heap and std::pop_heap. The following are the techniques I've already got covered in my implementation. I only came up with the last 2 myself, though I doubt that those are new ideas:

(Edit: added section on memory optimization)

Start indexes at 1
Look at the Wikipedia implementation notes for binary heaps. If the heap's root is placed at index 0, then the formulas for parent, left-child and right-child of the node at index n are respectively (n-1)/2, 2n+1 and 2n+2. If you use a 1-based array then the formulas become the simpler n/2, 2n and 2n + 1. So parent and left-child are more efficient when using a 1-based array. If p points to a 0-based array and q = p - 1 then we can access p[0] as q[1] so there is no overhead in using a 1-based array.

Make pop/removal move element to bottom of heap before replacement with leaf
Pop on a heap is frequently described by replacing the top element by the left-most bottom leaf and then moving it down until the heap property is restored. This requires 2 comparisons per level that we go by, and we are likely to go far down the heap since we moved a leaf to the top of the heap. So we should expect a little less than 2 log n comparisons.

Instead, we can leave a hole in the heap where the top element was. Then we move that hole down the heap by iteratively moving the larger child up. This requires only 1 comparison per level that we go past. In this way the hole will become a leaf. At this point we can move the right-most bottom leaf into the position of the hole and move that value up until the heap property is restored. Since the value we moved was a leaf we don't expect it to move very far up the tree. So we should expect a little more than log n comparisons, which is better than before.

Support replace-top
Suppose you want to remove the max element and also insert a new element. Then you can do either of the removal/pop implementations described above, but instead of moving the right-most bottom leaf, you use the new value you wish to insert/push. (When most operations are of this kind I've found that a tournament tree is better than a heap, but otherwise the heap is slightly better.)

Make sizeof(T) a power of 2
The parent, left-child and right-child formulas work on indexes and they cannot be made to work directly on pointer values. So we are going to be working with indexes and that implies looking up values p[i] in an array p from an index i. If p is a T* and i is an integer, then

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i

and the compiler has to perform this computation to get p[i]. sizeof(T) is a compile-time constant, and the multiplication can be done more efficiently if sizeof(T) is a power of two. My implementation got faster by adding 8 padding bytes to increase sizeof(T) from 24 to 32. Reduced efficiency of the cache probably means that this is not a win for sufficiently large data sets.

Pre-multiply indexes
This was a 23% performance increase on my data set. The only thing we ever do with an index other than finding parent, left-child and right-child is to look the index up in an array. So if we keep track of j = sizeof(T) * i instead of an index i, then we could do a lookup p[i] without the multiplication that is otherwise implicit in evaluating p[i] because

&(p[i]) == static_cast<char*>(p) + sizeof(T) * i == static_cast<char*>(p) + j

Then the left-child and right-child formulas for j-values become respectively 2*j and 2*j + sizeof(T). The parent formula is a little more tricky, and I haven't found a way to do it other than converting the j-value to an i-value and back like so:

parentOnJ(j) = parent(j/sizeof(T))*sizeof(T) == (j/(2*sizeof(T))*sizeof(T)

If sizeof(T) is a power of 2 then this will compile to 2 shifts. That is 1 operation more than the usual parent using indexes i. However we then save 1 operation on lookup. So the net effect is that finding the parent takes the same amount of time this way, while lookup of left-child and right-child becomes faster.

Memory optimization

The answers of TokenMacGuy and templatetypedef point out memory based optimizations that reduce cache misses. For very large data sets or infrequently used priority queues, parts of the queue can be swapped out to disk by the OS. In that case it is worth it to add a lot of overhead to make optimal use of the cache because swapping in from disk is very slow. My data easily fits in memory and is in continuous use, so no part of the queue will likely be swapped to disk. I suspect that this is the case for most uses of priority queues.

There are other priority queues that are designed to make better use of the CPU cache. For example a 4-heap should have fewer cache misses and the amount of extra overhead is not that much. LaMarca and Ladner report in 1996 that they get 75% performance improvement from going to aligned 4-heaps. However, Hendriks reports in 2010 that:

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.

Question
Are there more techniques than these?

解决方案

An interesting paper/article on this topic considers the behavior of caching/paging on the overall layout of the heap; The idea being that it's vastly more costly to pay for a cache miss or page in than nearly any other part of a datastructure's implementation. The paper discusses a heap layout that addresses this.

You're Doing It Wrong by Poul-Henning Kamp

这篇关于高效实现二进制堆的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！