在O（1）时间查找最大堆的第10个最大元素时间

Question

我试图实现一个算法来查找具有n个不同元素的最大堆的第10个最大元素O（1 ） 时间。

我试图绘制它并使用heap属性，但随着我在堆中更深入，它变得越来越复杂。这是我所做的草案，以及我坚持的地方 - 从我们具有不同元素和堆属性的事实来看，我们知道父项始终比子项大。因此根是最大的元素。下一个最大元素是根子之间的更大元素。

编辑：我还想过比较大的儿子和其他父母的儿子。如果它们中的至少一个大于另一个父亲，那么通过heap属性，我们继续从最大的儿子那里继续这样做，直到我们有10个元素，但它并不总是如此，因为当我们深入时可能没有元素，现在我们需要再次回来。

任何解释，甚至伪代码将非常appriciated。

在此先感谢！

Answer 1

一个可能的解决方案，很可能不是禁食，但仍然O（1）将提取所有堆的顶部元素（查看树）到10的水平。然后排序并返回第十个要素。

注意，提取元素的数量是有界的，这导致了O（1）的努力。