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