iterator - 在二叉堆上实现迭代器

Question

我正在寻找一种在二进制堆(最大或最小)上实现迭代器的方法。

也就是说，通过第i次使用它的nextNode()函数，可以获得堆中的第i个(大于或小于)元素。

请注意，此操作发生时并未实际提取堆的根!

我最初的想法是:

• 实际上是提取i个元素，将它们压入堆栈，然后在获取第i个值后将它们插入回堆中。每次函数调用都需要 O(i*log(n))。
• 保留一个辅助排序数据结构，它可以在 O(1) 时间内查找下一个值，但更新将需要 O(n)。

我知道这些方法消除了使用堆的好处，因此我正在寻找更好的方法。

Answer 1

目前尚不清楚此解决方案的用例是什么，因此很难说什么会使解决方案可行或比任何其他解决方案更好。

也就是说，我建议对已经提出的一般“提取和排序”想法进行一些小改动:如果我们可以对数据结构进行更改，我们就可以就地进行排序。>

Wikipedia上建议的基本实现是一个部分排序的底层列表。我们可以(希望)一次性支付 O(n log(n)) 成本来在第一次时对堆进行排序>next() 被调用，之后 next 的时间为 O(1)。至关重要的是，完全排序的列表仍然是有效的堆。

此外，如果您考虑 heapsort算法，您可以从第二阶段开始，因为您从一个有效的堆开始。