二进制堆通常用于例如优先级队列。基本思想是不完全堆排序:您保持数据排序“刚好够”以快速取出顶部元素。
虽然 4 元堆在理论上比二元堆更糟糕,但它们也有一些好处。例如,它们将需要更少的堆重组操作(因为堆更浅),而显然需要在每个级别进行更多的比较。但是(这可能是他们的主要好处?)他们可能有更好的 CPU 缓存位置。所以一些消息来源说 3-ary 和 4-ary heaps在实践中优于 Fibonacci 和 binary heaps 。它们应该不会更难实现,额外的案例只是一些额外的if
案例。
有没有人为优先级队列尝试过 4 元堆(和 3 元)并进行了一些基准测试?在 Java 中,在对它们进行广泛的基准测试之前,您永远不知道它们是更快还是更慢。从我通过谷歌找到的所有信息来看,它可能完全依赖于语言和用例。一些消息来源说,他们发现 3-ary 对他们来说表现最好。
还有几点:
PriorityQueue
显然是一个二叉堆。但是例如该类也缺乏批量加载和批量修复支持,或者replaceTopElement
可以产生巨大的差异。例如批量加载O(n)
而不是O(n log n)
; 添加更大的候选集后,批量修复基本相同。跟踪堆的哪些部分是无效的可以用一个整数来完成。replaceTopElement
比poll
+便宜得多add
(只需考虑如何实施民意调查:用最后一个替换顶部元素)- 虽然堆对于复杂对象当然很受欢迎,但优先级通常是双精度值的整数。这不像我们在这里比较字符串。通常它是(原始)优先级
- PQ 通常仅用于获取前 k 个元素。例如,A*-search 可以在达到目标时终止。然后丢弃所有不太好的路径。所以队列永远不会完全清空。在 4 路堆中,顺序较少:大约是一半(父节点数量的一半)。因此,它将对这些不需要的元素施加较少的顺序。(如果您打算完全清空堆,这当然会有所不同,例如因为您正在进行堆排序。)