Phần tử lớn nhất trong Min Heap trong C++

Đề bài

Cho một min-heap (cây nhị phân hoàn chỉnh nơi cha ≤ con), tìm phần tử lớn nhất.

Nhận xét: Trong min-heap, phần tử lớn nhất chắc chắn nằm ở các nút lá (vì nút cha luôn ≤ con). Các nút lá nằm từ chỉ số n/2 đến n-1 (0-based).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

int getMaxElement(int* heap, int n) {
    int maxVal = heap[n / 2]; // nút lá đầu tiên
    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 << "Phan tu lon nhat = " << getMaxElement(heap, n) << endl;
    return 0;
}

Kết quả

Phan tu lon nhat = 55