C++ 中最大堆中的最小元素。

問題陳述

找出最大堆中最小的值。

讓我們考慮一下最大的堆。

在最大堆中，根節點的值始終大於它的子節點。由於這個屬性，我們可以得出該值將存在於一個葉子節點中。如果堆包含 n 個節點，則將有 ceil(n/2) 個葉子節點。

最大堆是一個完全二叉樹，因此可以表示為陣列。在這樣的堆中，第一個葉子節點將出現在 floor(n/2) 索引之後。因此，在我們的示例中，第一個葉子節點將出現在索引 5 處。

演算法

我們可以使用以下演算法來找到最大堆中的最小值 -

1. Find first leaf in a heap and consider its value as min
2. Iterate all remaining leaves and update min value if leaf with smaller value is found

示例

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;
int getMinElement(int *heap, int n){
   int minElement = heap[n / 2];
   for (int i = n / 2 + 1; i < n; ++i) {
      minElement = min(minElement, heap[i]);
   }
   return minElement;
}
int main(){
   int heap[] = {120, 90, 100, 70, 75, 80, 60, 25, 40, 35};
   cout << "Min value: " << getMinElement(heap, SIZE(heap)) << "\n";
   return 0;
}

輸出

當您編譯並執行上述程式時。它會生成以下輸出 -

Min value: 25

Narendra Kumar

更新時間：2019-09-23

335 瀏覽次數

開啟你的 職業生涯

完成課程以獲得認證

開始