Sự khác biệt cơ bản giữa Max-Heap và Min-Heap là gì và trong trường hợp nào một lập trình viên Junior nên chọn sử dụng cấu trúc Min-Heap thay vì Max-Heap khi giải quyết bài toán thực tế?

Question

Accepted Answer

Bản chất cấu trúc Heap
Heap là một cấu trúc dữ liệu dạng cây nhị phân hoàn chỉnh (Complete Binary Tree) thỏa mãn tính chất Heap:

Max-Heap: Giá trị của nút cha luôn lớn hơn hoặc bằng giá trị của các nút con. Phần tử lớn nhất luôn nằm ở gốc (Root).
Min-Heap: Giá trị của nút cha luôn nhỏ hơn hoặc bằng giá trị của các nút con. Phần tử nhỏ nhất luôn nằm ở gốc (Root).

Trường hợp sử dụng Min-Heap
Một lập trình viên Junior nên chọn Min-Heap khi cần truy xuất hoặc loại bỏ phần tử có giá trị nhỏ nhất một cách liên tục với độ phức tạp thời gian O(1) cho việc đọc và O(log N) cho việc thêm hoặc xóa.
Ví dụ thực tế:

Bài toán quản lý hàng đợi ưu tiên (Priority Queue) mà các tác vụ có số thứ tự ưu tiên nhỏ hơn sẽ được xử lý trước.
Thuật toán đường đi ngắn nhất Dijkstra, nơi cần liên tục tìm đỉnh có khoảng cách ngắn nhất từ đỉnh nguồn.
Bài toán tìm K phần tử lớn nhất trong một luồng dữ liệu (Streaming Data) bằng cách duy trì một Min-Heap có kích thước cố định là K.

Sự khác biệt cơ bản giữa Max-Heap và Min-Heap là gì và trong trường hợp nào một lập trình viên Junior nên chọn sử dụng cấu trúc Min-Heap thay vì Max-Heap khi giải quyết bài toán thực tế?

Bản chất cấu trúc Heap

Làm Chủ Phỏng Vấn & Nâng Cao Trình Độ Chuyên Nghiệp

Tải Tuyển Tập 100+ Câu Hỏi Phỏng Vấn Chuyên Sâu (PDF)

Cần Mentor Phỏng Vấn Thử 1-1 & Tối Ưu CV?

Kiểm Tra CV Chuẩn ATS Miễn Phí

Câu hỏi heaps and maps liên quan cùng chủ đề