Computer >> Máy Tính >  >> Lập trình >> C ++

Phần tử tối đa trong đống tối thiểu trong C ++

Tuyên bố vấn đề

Đưa ra một đống tối thiểu, hãy tìm phần tử tối đa trong đó.

Ví dụ

Nếu đống đầu vào là -

Phần tử tối đa trong đống tối thiểu trong C ++

Khi đó, phần tử tối đa là 55

Thuật toán

  • Trong heap tối thiểu, nút cha sẽ ít hơn nút con của nó. Do đó, chúng tôi có thể kết luận rằng một nút không phải là nút lá không thể là cực đại.
  • Tìm kiếm phần tử tối đa trong các nút lá

Ví dụ

Bây giờ chúng ta hãy xem một ví dụ -

#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;
}

Đầu ra

Maximum element = 55