在O(1)时间内找到Max-Heap的第10个最大元素

Question

我正在尝试实现一个算法，在O(1)时间内找到具有n个不同元素的Max-Heap的第10个最大元素。

我试图绘制它并使用heap属性，但随着我在heap中越深入，它就变得越来越复杂。这是我做的一个草稿，也是我坚持的地方--因为我们有不同的元素和heap属性，我们知道父元素总是大于它的子元素。因此，根是最大的元素。下一个最大元素是根的子元素之间的较大元素。

编辑:我也考虑过将较大者的儿子与另一位父母的儿子进行比较。如果它们中至少有一个大于另一个父元素，根据heap属性，我们从最大的子元素开始继续，直到我们有10个元素，但这并不总是正确的，因为当我们深入下去时，可能没有元素，现在我们需要再次返回。

任何解释，甚至是伪代码，都将非常有用。

提前感谢！

Answer 1

一种可能的解决方案，很可能不是fasted的，但仍然是O(1)是提取堆的所有顶部元素(以树的形式)到10的级别，然后对它们进行排序并返回第10个元素。

请注意，提取的元素的数量是有界的，这导致O(1)的努力。