我正在使用此处找到的配对堆实现：https ://github.com/jemalloc/jemalloc/commits/dev/include/jemalloc/internal/ph.h
尽管有时我需要遍历堆中的 N min 值（其中 N 受堆中元素的数量限制，但通常更少）。有没有有效的方法来做到这一点？
我目前的方法是调用remove_first()N 次，然后通过insert().
问问题
33 次
1 回答
1
您的方法是O(k log n)，其中k是您要打印的项目数，并且n是堆中的元素数。看起来这些操作在您正在使用的实现中已经得到了相当广泛的优化。有一种方法可以用另一个堆遍历堆来解决您的目标O(k log k)，这在打开日志因子k而不是n. 该方法相当简单：维护一个最小堆的值（带有指向树中节点的指针），初始化为根（这是堆中的最小值）。然后，您可以弹出辅助堆并将当前节点的子节点插入主堆，这会更快，因为队列中只有可能是下一个最小值的节点（它们是您拥有的节点的邻居）到目前为止）。
虽然这种方法的大 O 复杂性在技术上更好，但在实践中几乎肯定会慢得多。这个最小配对堆的实现似乎非常有效，几乎可以肯定它会超过创建辅助堆和执行此搜索的开销。更不用说可能引入错误的额外代码复杂性，这可能不值得。
我很确定你不能做得比O(k log k). 我对此的直觉是，如果你能做得更好，排序的时间可能会不断减少，但基于比较的排序 (iirc) 已被证明不可能比O(n log n). 这种直觉可能是错误的，但我认为它可能非常接近事实。祝你好运！
于 2022-03-01T00:46:49.900 回答