在O（1）時間查找最大堆的第10個最大元素時間

Question

我試圖實現一個算法來查找具有n個不同元素的最大堆的第10個最大元素O（1 ） 時間。

我試圖繪製它並使用heap屬性，但隨着我在堆中更深入，它變得越來越複雜。這是我所做的草案，以及我堅持的地方 - 從我們具有不同元素和堆屬性的事實來看，我們知道父項始終比子項大。因此根是最大的元素。下一個最大元素是根子之間的更大元素。

編輯：我還想過比較大的兒子和其他父母的兒子。如果它們中的至少一個大於另一個父親，那麼通過heap屬性，我們繼續從最大的兒子那裏繼續這樣做，直到我們有10個元素，但它並不總是如此，因爲當我們深入時可能沒有元素，現在我們需要再次回來。

任何解釋，甚至僞代碼將非常appriciated。

在此先感謝！

Answer 1

一個可能的解決方案，很可能不是禁食，但仍然O（1）將提取所有堆的頂部元素（查看樹）到10的水平。然後排序並返回第十個要素。

注意，提取元素的數量是有界的，這導致了O（1）的努力。