You are implementing a task scheduler that stores 1,000,000 task priorities in a binary min-heap backed by an array. The team now asks you to also report the task with the HIGHEST priority value (the maximum element), without changing the data structure. Assuming no extra bookkeeping is added, what is the worst-case time complexity of finding that maximum element?

Question

Accepted Answer

Min-heap chỉ đảm bảo mỗi nút nhỏ hơn hoặc bằng các con của nó, nên phần tử lớn nhất chắc chắn nằm ở một lá nào đó nhưng không xác định được là lá nào; phải duyệt khoảng n/2 lá → O(n). Đáp án a sai vì mảng heap không được sắp xếp hoàn toàn, phần tử cuối không nhất thiết là lớn nhất; b sai vì không có thuộc tính nào hướng dẫn đường đi tới max (khác với max-heap tìm min); d sai vì không cần sắp xếp lại, chỉ cần một lần quét tuyến tính.

Câu hỏi hôm nay