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