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

Tuyên bố vấn đề

Tìm phần tử có giá trị nhỏ nhất trong đống tối đa.

Hãy để chúng tôi xem xét đống tối đa bên dưới.

Trong heap tối đa, giá trị của nút gốc luôn lớn hơn nút con của nó. Do thuộc tính này, chúng ta có thể kết luận rằng giá trị sẽ có ở một trong các nút lá. Nếu đống chứa n nút thì sẽ có (n / 2) lá.

Max heap là một cây nhị phân hoàn chỉnh do đó nó có thể được biểu diễn trong một mảng. Trong đống như vậy, lá đầu tiên sẽ xuất hiện sau chỉ số tầng (n / 2). Vì vậy, trong ví dụ của chúng tôi, lần nghỉ phép đầu tiên sẽ có mặt ở chỉ số 5. ​​

Thuật toán

Chúng ta có thể sử dụng thuật toán dưới đây để tìm giá trị tối thiểu trong một đống tối đa -

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

Ví dụ

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

Đầu ra

Khi bạn biên dịch và thực thi chương trình trên. Nó tạo ra kết quả sau -

Min value: 25