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

问题陈述

给定一个最小堆，找到其中的最大元素。

示例

如果输入堆为：

那么最大元素为 55

Explore our latest online courses and learn new skills at your own pace. Enroll and become a certified expert to boost your career.

算法

  • 在最小堆中，父节点将小于其子节点。因此，我们可以得出结论，非叶节点不可能是最大值。
  • 在叶节点中搜索最大元素

示例

我们现在来看一个示例：

 实时演示

#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

更新于：2019 年 12 月 31 日

298 次访问

开启你的 职业生涯

完成课程后取得认证

开始
广告