堆數據結構

Question

嘗試考慮位置的下限，這是max-heap中第n個最大的鍵。假設堆放置在數組中。上限的最小值（2^n-2，數組大小-1）我認爲，但總是下限爲0？

Answer 1

問題的初始調查揭示了n和下限和上限之間的以下關係式（假設有在堆14個元件）

n lb up 
1 1 1 
2 2 3 
3 2 7 
4 2 14 
9 3 14 
10 4 14 
12 5 14 
13 6 14 
14 8 14 

要確定是可能的量比較大的元件的數目元素放在堆數組的特定位置，計算以該位置爲根的子樹的大小。 注意，計算被向後執行：這兩個數然後由式

# of elements possible larger = total number of elements - size of subtree - 1 

EDIT有關。給定數組/堆中的位置，可以確定如果堆被分類，值將在哪個位置。給定的節點處的堆可以被劃分成三個分區：被保證是比當前的元件大

1. 元素（父，父母父，...）被保證是
2. 元素小於當前元素（根植於當前元素的子樹）
3. 剩餘的元素可以大於或小於當前元素。

如果我們看一下用14族元素的實例堆，想要確定在第六位置的可能值的範圍內，基團如下：

• 組1包含兩個元素（3， 1）
• 組2包含兩個元素（12,13）
• 組3包含剩餘的九個元素（不包括當前值）（2,4,5,7,8,9,10,11,14）

因此，下限是3（組1中的元素數+1），而上限是11（組1中的元素數量+組3中元素數量+1）。