Binomial Heap là tập hợp các Binomial Tree. Cây nhị thức Bk được định nghĩa đệ quy. B0 chỉ gồm một nút.
Bk bao gồm hai Bk-1 liên kết: gốc của cái này là con trái nhất của gốc cái kia.
Một số Binomial Heap:
Đặc điểm cây nhị thức:
- Bk có 2^k nút.
- Chiều cao là k.
- Có chính xác C(k, i) nút ở độ sâu i (0 ≤ i ≤ k).
Binomial Heap
Binomial heap H là tập hợp các cây nhị thức. Có tính chất:
- Mỗi cây trong H có thứ tự heap (khóa nút ≥ khóa cha).
- Tối đa một cây trong H có gốc bậc (degree) cho trước.
Ví dụ Binomial Heap
Heap H này gồm B0, B2, B3 với 1, 4, 8 nút. Tổng n = 13. Gốc các cây liên kết bằng danh sách theo bậc tăng dần.