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

問題陳述

給定一個最小堆，找到其中的最大元素。

示例

如果輸入堆為：

那麼最大元素為 55

演算法

• 在最小堆中，父節點將小於其子節點。因此，我們可以得出結論，非葉節點不可能是最大值。
• 在葉節點中搜索最大元素

示例

我們現在來看一個示例：

 即時演示

#include <bits/stdc++.h>
using namespace std;
int getMaxElement(int *heap, int n) {
   int maxVal = heap[n / 2];
   for (int i = n / 2 + 1; i < n; ++i) {
      maxVal = max(maxVal, heap[i]);
   }
   return maxVal;
}
int main() {
   int heap[] = {15, 27, 22, 35, 29, 55, 48}; int n = sizeof(heap) / sizeof(heap[0]);
   cout << "Maximum element = " << getMaxElement(heap, n) << endl;
   return 0;
}

輸出

Maximum element = 55

Narendra Kumar

更新於：2019 年 12 月 31 日

298 次訪問

開啟你的 職業生涯

完成課程後取得認證

開始