Tài liệu Hàng ưu tiên với phép toán hợp nhất

Trong chương này chúng ta mở rộng KDLTT hàng ưu tiên bằng cách thêm vào hai phép toán: phép toán hợp nhất (Merg) và phép toán giảm khoá (Decreasekey). Các phép toán này là rất cần thiết trong thiết kế thuật toán cho các bài toán tối ưu, chẳng hạn các thuật toán đồ thị như tìm đường đi ngắn nhất (thuật toán Dijkstra), tìm cây bao trùm ngắn nhất (thuật toán Prim). Đầu tiên chúng ta sẽ cài đặt KDLTT hàng ưu tiên với phép toán hợp nhất bởi cây thứ tự bộ phận (binary heap), sau đó chúng ta sẽ xây dựng một CTDL tự điều chỉnh, đó là cây nghiêng (skew heap), để cài đặt hàng ưu tiên với phép toán hợp nhất và sử dụng kỹ thuật phân tích trả góp để đánh giá thời gian chạy của các phép toán hàng ưu tiên trên CTDL này.