Phần tử nhỏ nhất trong max heap trong C++

Đề bài

Tìm phần tử có giá trị nhỏ nhất trong max heap.

Trong max heap, giá trị gốc luôn lớn hơn con. Do đó phần tử nhỏ nhất sẽ nằm ở các nút lá. Nếu heap có n nút thì có ceil(n/2) lá. Max heap là cây nhị phân hoàn chỉnh, biểu diễn bằng mảng. Lá đầu tiên nằm sau chỉ số floor(n/2).

Thuật toán

1. Tìm lá đầu tiên trong heap, coi giá trị đó là min
2. Duyệt các lá còn lại, cập nhật min nếu tìm thấy giá trị nhỏ hơn

Ví dụ mã C++

#include <iostream>
#define SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
using namespace std;

int layPhanTuNhoNhat(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 << "Giá trị nhỏ nhất: " << layPhanTuNhoNhat(heap, SIZE(heap)) << "\n";
    return 0;
}

Kết quả đầu ra

Giá trị nhỏ nhất: 25