C++の最大ヒープの最小要素。

問題の説明

最大ヒープの値が最小の要素を見つけます。

最大ヒープ以下を考えてみましょう。

ルートノードの最大ヒープ値は、常にその子ノードよりも大きくなります。このプロパティにより、値はリーフノードの1つに存在すると結論付けることができます。ヒープに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