Pairing Heap và hàng đợi ưu tiên
Pairing heap được triển khai cho việc sử dụng hoàn hảo của hàng đợi ưu tiên (priority queue). Hàng đợi ưu tiên theo dõi phần tử nhỏ nhất của một tập hợp đối tượng, nên mỗi khi lấy phần tử ra khỏi hàng đợi, nó luôn là giá trị nhỏ nhất. Hàng đợi ưu tiên thường được dùng trong thuật toán Dijkstra để tính đường đi ngắn nhất trong đồ thị.
Ưu điểm của Pairing Heap
Pairing heap được coi là "hoàn hảo" vì chúng dễ triển khai và hoạt động tốt trong ứng dụng thực tế. Cụ thể, chúng hoạt động xuất sắc về thời gian trung bình (amortized time). Nghĩa là dù một thao tác riêng lẻ có thể tốn thời gian dài, nhưng tổng thời gian của tất cả thao tác trên toàn vòng đời hàng đợi là nhanh. Pairing heap dễ viết code hơn và thường chạy nhanh hơn Fibonacci heap.
Cấu trúc và các thao tác cơ bản
Pairing heap có các thuộc tính đơn giản. Mỗi heap liên kết với một đối tượng hoặc giá trị. Mỗi heap cũng được trang bị một tập hợp các heap con. Giá trị của đối tượng luôn lớn hơn (hoặc nhỏ hơn) giá trị của các heap con của nó.
Heap có một vài thao tác cơ bản:
- min(heap) – Lấy giá trị nhỏ nhất. Hàm này rất đơn giản, chỉ nhìn giá trị đỉnh của heap.
- merge(heap1, heap2) – Gộp hai heap. Thêm heap có giá trị lớn hơn vào danh sách con của heap kia. Hàm này cũng rất nhanh.