2017-04-11 165 views
0

有人能告訴我哪些是二進制堆(最大值),哪些是最小優先級隊列,以及爲什麼/爲什麼不是這樣?我會在數組中發佈它們,因爲我不知道如何在這裏發佈圖片,這意味着這個位置是空白的。二進制堆和最小優先級隊列的

這裏我們去:[8,6,7,4,6​​,6,x],[4,5,4,7,8,4,6],[,4,4,5,7, x,x,6]

我會假設第一個是二進制堆,而另外兩個是最小優先級隊列,但根據解決方案,我錯了。但解決方案可能是錯誤的,所以如果你知道哪一個是哪個請解釋給我。

在此先感謝。

回答

0

那麼,第一個可能是一個二進制最大堆。也就是說,樹應該是這樣的:

  8 
     6  7 
    4 6 6 

第二個是一個二元分堆:

  4 
     5  4 
    7 8 4 6 

第三不能是一個二元堆,因爲它不符合形狀屬性。也就是說,將對應於:

  4 
    4  5 
    7 x x 6 

在二進制堆,最下面一行留下填充。這棵樹沒有被填滿。

所以第一個是二進制最大堆。第二個是二進制最小堆,它也可以被看作是一個面向min的優先級隊列。我不知道該怎麼稱呼第三個。這不是一個有效的最小堆,它不是一個最小優先級隊列的順序表示,因爲7在6之前。

至少,這是基於我對二進制堆和優先級隊列的理解。