Binomial Heap là mở rộng của Binary Heap, cung cấp phép hợp nhất (merge/union) nhanh hơn cùng các phép toán khác của Binary Heap.
Binomial Heap được xem như tập hợp các Binomial Tree (Cây nhị thức).
Binomial Tree là gì?
Cây nhị thức bậc k xây từ hai cây nhị thức bậc k-1, lấy một làm con trái nhất của cái kia.
Đặc tính cây nhị thức bậc k:
- Số nút chính xác là 2k.
- Độ sâu là k.
- Có đúng kCi nút ở độ sâu i (i = 0..k).
- Gốc có bậc k, các con của gốc là các cây nhị thức bậc k-1, k-2, ..., 0 từ trái sang phải.
Binomial Heap
Là tập hợp các cây nhị thức, mỗi cây tuân theo tính chất Min Heap. Với mỗi bậc, tối đa có một cây nhị thức.
Ví dụ
Binomial Heap 12 nút = tập hợp 2 cây nhị thức bậc 2 và 3 (từ trái sang phải).
Binomial Heap và biểu diễn nhị phân
Binomial Heap có m nút → số cây nhị thức = số bit 1 trong biểu diễn nhị phân của m. Ví dụ m=13 (1101) → 3 bit 1 → 3 cây nhị thức. Bậc các cây tương ứng vị trí bit 1. Do đó có O(log m) cây trong heap.
Các phép toán
- union() – phép toán chính, gộp hai Binomial Heap thành một.
- insert(h, K) – Tạo heap đơn lẻ với khóa K, gọi union với h.
- getMin(h) – Duyệt danh sách gốc các cây, trả về khóa nhỏ nhất. O(log m), có thể cải tiến O(1) bằng con trỏ gốc nhỏ nhất.
- extractMin(h) – Gọi getMin(), xóa nút nhỏ nhất, tạo heap mới từ các cây con, gọi union. O(log m).
- delete(h) – Giảm khóa xuống -∞, gọi extractMin().
- decreaseKey(h) – So sánh khóa giảm với cha, nếu cha lớn hơn thì hoán đổi, lặp đến gốc. O(log m).