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

更新时间：2019-09-23

335 浏览次数

开启你的 职业生涯

完成课程以获得认证

开始
广告