Giới thiệu
Pairing heap là một loại cấu trúc dữ liệu heap với triển khai đơn giản và hiệu suất trung bình (amortized) thực tế tuyệt vời.
Pairing heap là cấu trúc cây đa đường (multiway tree) có thứ tự heap, có thể coi là phiên bản đơn giản hóa của Fibonacci heap.
Chúng được xem là "lựa chọn vững chắc" (robust choice) để triển khai các thuật toán như Prim's MST, và hỗ trợ các thao tác sau (giả sử min-heap):
- find-min – Trả về phần tử đỉnh của heap.
- meld – So sánh hai phần tử gốc, phần tử nhỏ hơn giữ làm gốc kết quả, phần tử lớn hơn và cây con của nó được thêm làm con của gốc này.
- insert – Tạo heap mới cho phần tử chèn và meld vào heap gốc.
- decrease-key (tùy chọn) – Loại bỏ cây con gốc tại khóa cần giảm, thay khóa bằng khóa nhỏ hơn, sau đó meld kết quả trở lại heap.
- delete-min – Loại bỏ gốc và thực hiện meld lặp lại các cây con cho đến khi chỉ còn một cây. Các chiến lược gộp khác nhau được sử dụng.
Mỗi nút có con trỏ tới con trái, và con trái trỏ tới anh em kế tiếp của con đó.
Ví dụ minh họa
Phân tích độ phức tạp thời gian
Phân tích độ phức tạp thời gian của pairing heap chủ yếu lấy cảm hứng từ cây splay (splay trees). Thời gian trung bình cho mỗi delete-min được coi là O(log n), trong khi các thao tác find-min, meld và insert chạy trong O(1) thời gian trung bình.