Mở đầu

Bạn đã bao giờ cần tìm phần tử lớn nhất hoặc nhỏ nhất trong một danh sách một cách nhanh chóng chưa? Hoặc bạn cần xử lý nhiều lần thêm – xóa phần tử rồi cập nhật thứ tự ưu tiên? Nếu có—đây chính là lúc “Heap” (ngăn xếp đặc biệt) trở nên siêu hữu dụng. Nội dung này sẽ giải thích rõ từ gốc đến ngọn về Heap, giúp bạn hiểu và áp dụng dễ dàng trong PHP hoặc bất cứ ngôn ngữ nào khác.

Nội dung chính

1. Heap là gì?

Heap là một loại cấu trúc dữ liệu dạng cây nhị phân, nhưng có hai quy tắc riêng biệt cần nhớ:

Min-Heap: cha luôn có giá trị nhỏ hơn hoặc bằng con
Max-Heap: cha luôn có giá trị lớn hơn hoặc bằng con (Đây gọi là “heap property”) (doeken.org, Wikipedia).
Cây nhị phân đủ (complete binary tree): tức là các tầng được lấp đầy từ trái sang phải, chỉ trừ tầng cuối cùng có thể không đầy. (doeken.org, Wikipedia).

Ví dụ đời thường:

Min-Heap như việc bạn luôn giữ đầu danh sách là người ít tuổi nhất – cứ ai đến được xét từ nhỏ nhất.
Max-Heap giống như cuộc đua, người về đích nhanh nhất luôn đứng đầu.

2. Cấu trúc lưu heap bằng mảng

Bạn không cần pointer—chỉ một mảng đơn giản!

Nếu bắt đầu từ chỉ số 0:
- Con trái của node i nằm tại 2*i + 1
- Con phải: 2*i + 2
- Cha của node i: (i – 1) // 2 (Codecademy, GeeksforGeeks)

Ví dụ: Mảng [10, 4, 5, 1, 2] tạo thành Max-Heap:

3. Các thao tác quan trọng

Chèn (Insert): thêm phần tử vào cuối mảng rồi "bubble-up" để giữ heap đúng quy tắc (Wikipedia, GeeksforGeeks).
- Ví dụ: chèn 8 vào Max-Heap [5, 3, 4] → thêm cuối thành [5,3,4,8], “bubble-up” hoán đổi dần đến đúng vị trí (bên trên).
Lấy & xóa phần tử gốc (Extract-min/max):
- Lấy phần tử đầu (nhỏ nhất/ lớn nhất), thay bằng phần tử cuối, rồi “sift-down” để heapify lại (Wikipedia, GeeksforGeeks).

Minh họa bằng code PHP (Max-Heap):

$heap = []; // mảng rỗng

// chèn phần tử
function insert(&$heap, $val) {
    $heap[] = $val;
    $i = count($heap) - 1;
    while ($i > 0) {
        $p = intval(($i - 1) / 2);
        if ($heap[$i] <= $heap[$p]) break;
        // đổi chỗ
        list($heap[$i], $heap[$p]) = [$heap[$p], $heap[$i]];
        $i = $p;
    }
}

Sau mỗi bước: mình giải thích rõ ràng vị trí, tại sao lại đổi chỗ, tránh dùng thuật ngữ "heapify" gây nhầm lẫn.

Ví dụ thực tế minh hoạ (ít nhất hai)

Hàng đợi ưu tiên (priority queue): muốn xử lý công việc theo mức ưu tiên cao nhất trước—rất thích hợp dùng Max-Heap để luôn "lấy" phần tử quan trọng nhất nhanh nhất.
Thuật toán Dijkstra (tìm đường ngắn nhất): cần thường xuyên chọn nút có khoảng cách nhỏ nhất trong nhánh tiếp theo—Min-Heap là trợ thủ đắc lực.

Phần tương tác nhẹ

Thử thách nhỏ: Hãy thử xây một Min-Heap trong PHP từ mảng [3, 1, 4, 1, 5], rồi chèn thêm số 0, bạn sẽ nhận được thứ tự như thế nào?
Câu hỏi gợi mở: Heap giống và khác gì so với cây tìm kiếm nhị phân (BST)? Bạn cảm thấy đâu là tình huống nó phù hợp hơn?

Kết luận

Tóm tắt: Heap là cấu trúc cây nhị phân đủ, tuân theo quy tắc Min hoặc Max, cực mạnh trong việc tìm phần tử min/max nhanh.
Lời khuyên: Khi mới học, hãy vẽ sơ đồ hoặc viết mảng sau mỗi thao tác, giúp bạn hiểu rõ quá trình “bubble-up” và “sift-down”.
Học tiếp: Sau Heap, bạn có thể tìm hiểu về “Heap Sort” (thuật toán sắp xếp biểu diễn thành heap) hoặc các biến thể khác như Fibonacci Heap.

Tài liệu tham khảo

Heaps explained in PHP – doeken.org (doeken.org)
Heap (data structure) – Wikipedia (giới thiệu tổng quan về heap và ứng dụng) (Wikipedia)
Min/Max-Heap operations và phân tích – GeeksforGeeks / Programiz (GeeksforGeeks, Programiz)

Hy vọng sau bài viết này, bạn sẽ vững tin hơn trong việc khám phá cấu trúc dữ liệu và tiếp tục chinh phục những khái niệm thú vị khác!

Heaps trong PHP