具有相同元素的最大和最小堆

Question

考慮以下示例。我將隨機數添加到最小堆中，同時我將相同數字以相同順序添加到最大堆中。所以最後這兩堆將有相同的數字，其中一個是最小堆，另一個是最大堆。

現在，這裏的問題：

如果我決定從最大堆取出的最大元素，將從最大堆總是在最小堆的底部是最大的元素？如果不是，那麼另一個問題是，如果我想從最小堆中刪除最大元素並將其與最小堆的最後一個元素進行交換，刪除最後一個元素，我是否需要運行必須比較該開關元素的操作與他的孩子，以修復分堆？或者將它總是與父母進行比較以修復最小堆？

Answer 1

根據定義的最大堆，根總是大於它的孩子。然而，在兒童中沒有特定的順序，所以左側的孩子並不總是大於右側，反之亦然。 max heap的最大元素，即根，必須位於最小堆中的葉子上。我們不知道哪一片葉子，這取決於元素的配置。 （即插入這些元素的順序，因爲通常插入的元素是從樹的最左側到最右側填充的）