在二进制堆上实现迭代器

Question

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

也就是说，通过第i次使用其nextNode（）函数，可以获得堆中第i个（更大或更小的）元素。

请注意，此操作是在没有实际提取堆根的情况下发生的！

我最初的想法是：

• 实际上提取i元素，将它们压入堆栈，然后在获得第i个值后将它们重新插入堆中。每个函数调用都需要O（i * log（n））。
• 保留一个辅助排序的数据结构，该结构可以允许在O（1）中查找下一个值，但是更新将占用O（n）。

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

Answer 1

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

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

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

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