有效最小堆積

-3

我需要確定該數組是否是有效最小堆積。如果不是，哪些值不合適？我已經對堆很困惑，所以這對我來說很困難。任何人都可以向我解釋一下嗎？有效最小堆積

[0,6，2，26，24，22，20，48，46，44]

來源

2015-04-06 William Diuguid

在基於陣列最小堆的項目被存儲在一個完整的二叉樹。假設基於0的數組，這意味着索引i中項目的左側子項將在索引2i + 1中，右側子項將位於索引2i + 2中。

最小堆不變是每個節點都小於它的後代。因此，爲了檢查堆是否合法，您需要做的就是遍歷所有內部節點，並確保這個條件成立，即索引i中的每個內部堆節點a[i] < a[2*i + 1] && a[i] < a[2*i + 2]。

來源

2015-04-06 22:41:05

如果有幫助，這裏是更多圖形化的堆。不變量是每個父母都小於兩個孩子。

  0 
     6   2 
    26  24 22  20 
48 46 44

正如你可以看到每個節點都比它的父節點大，所以這是一個有效的最小堆。

來源

2015-04-06 22:46:17 Guvante

我現在明白這個問題。但是，現在我必須添加和從最小堆刪除初始配置：[0,2,4,6,8,10,12,14] 插入1 刪除4 刪除0 插入3 –

我認爲插入1會產生[0,1,4,2,8,10,12,14,6] –

@WilliamDiuguid：插入意味着「追加到數組的末尾，並與父親交換，而父母大於自我」這符合你的例子。刪除的意思是「用最後一個元素交換根節點，並將該元素與其子元素中最小的元素交換，直到它是一個葉子或小於其子元素」。因爲交換的6碰巧在正確的位置，所以移除4會是[0,1,6,2,8,10,12,14]。 – Guvante

堆可以作爲數組實現，因爲單元格之間的順序是this。現在您應該遍歷堆，每當您訪問一個節點時，請驗證它是否大於其父項，如heap所要求的那樣。

來源

2015-04-06 22:48:17 avim

有效最小堆積

回答

相關問題