二进制堆通常用于例如优先级队列中。基本思想是不完整的堆排序：将数据排序为“恰好足够”，以快速获取顶部元素。
虽然4元堆在理论上比二进制堆差，但它们确实也有一些好处。例如，它们将需要较少的堆重组操作（因为堆要浅得多），而显然需要在每个级别进行更多比较。但是（这可能是它们的主要好处？）它们可能具有更好的CPU缓存局部性。因此，一些消息人士说，在实践中3元和4元堆的性能优于Fibonacci和二进制堆。它们应该不难实施，其他情况只是一些其他if情况。
有没有人尝试过4进制堆（和3进制）作为优先级队列并进行了一些基准测试？在Java中，在广泛地对它们进行基准测试之前，您永远都不知道它们是更快还是更慢。从我通过Google发现的所有信息来看，这可能取决于语言和用例。一些消息来源说，他们发现3-ary对他们而言表现最佳。
还有几点：
PriorityQueue显然是二进制堆。但是，例如，该班级也缺乏批量装载和批量维修支持，否则replaceTopElement可能会产生很大的不同。批量加载例如是O(n)代替O(n log n); 在添加更多候选集之后，批量修复基本上是相同的。可以使用单个整数来跟踪堆的哪些部分无效。replaceTopElement比poll+ 便宜得多add（只要考虑一下民意调查的实现方式：将最后一个元素替换为最后一个）按照@ErichSchubert的建议，我从ELKI中获取了实现并将其修改为4进制堆。正确建立索引有点技巧，因为许多有关4进制堆的出版物都使用1索引数组的公式？
这是基于ELKI单元测试的一些早期基准测试结果。Double预先分配了200000个对象（以避免过多测量内存管理），并对其进行了重排。
作为热身，每个堆执行10次迭代，以对100次迭代进行基准测试，但我可能会尝试进一步扩大规模。10-30秒还不是真正可行的基准测试，OTOH我也应该尝试测量标准偏差。在每次迭代中，将200000个元素添加到堆中，然后再次轮询其中的一半。是的，工作量也可以变得更加复杂。
结果如下：
DoubleMinHeap：10.371DoubleMinHeap：12,356Heap<Double>：37458PriorityQueue<Double>：45.875因此，4-ary堆（可能还没有L1高速缓存对齐！）和原始双打的ELKI堆之间的差异不是太大。好吧，在10％-20％左右；这可能会更糟。
用于基本doubles的堆和用于Double对象的堆之间的差异要大得多。而且ELKI Heap确实确实比Java快得多PriorityQueue（但似乎差异很大）。但是，ELKI中有一个小“ bug”-至少原始堆尚未使用批量加载代码。它在那里，只是没有被使用，因为每个元素都会立即修复堆，而不是将其延迟到next poll()。我为实验进行了修复，基本上是删除了几行并添加了一个ensureValid();调用。此外，我还没有四元对象堆，并且我还没有包含ELKI的对象堆DoubleObjectMinHeap……要进行很多基准测试，我可能会尝试使用caliper。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句