堆 - 在未知輸入上執行DeleteMax操作 - 實現

Question

我需要您的幫助，試圖找出/獲取簡單證明的方法。

假設您給出了一個包含n個不同元素的最大堆，而x是深D堆中的一個元素（代表堆中的樹）。現在假設我們正在執行一系列DeleteMax操作。

1. 需要預先執行DeleteMax操作的最大數量是多少，直到x將從堆中提取出來。

2. 需要預先執行DeleteMax操作的最小數量是多少，直到x將從堆中提取出來爲止。

注：

我相信我還是設法通過specifing，在情況下，x和他的父母都在堆那麼x將d後提取的最大元素，證明第二個+1 DeleteMax操作（其中的D是專門提取父母的）。

我剛剛發現第一個這樣做不太好，我不確定我需要使用什麼方法才能正確地證明它。

Answer 1

我認爲你是對的。第二種情況會發生在只有x的父母和祖父母大於x時，而不是堂兄弟姐妹，等等......只有前輩們在直線上纔是根源。

只有x的孩子小於x時纔會發生第一種情況。因此，如果堆具有高度H，則最大值將是高度爲H的完整堆減去堆滿高度H-D的堆。