Meldable Priority Queues (Hàng đợi ưu tiên có thể gộp)
Định nghĩa
Randomized meldable heap (còn gọi là Meldable Heap hoặc Randomized Meldable Priority Queue) là một cấu trúc dữ liệu hàng đợi ưu tiên mà cấu trúc bên dưới là một cây nhị phân có thứ tự heap. Tuy nhiên, không có quy tắc cứng nhắc về hình dạng của cây nhị phân bên dưới.
Ưu điểm
- Cách tiếp cận này có nhiều tiện ích, ưu điểm hơn các cấu trúc dữ liệu tương tự.
- Cung cấp cách tiếp cận đơn giản hơn các cấu trúc dữ liệu khác.
- Tất cả thao tác cho randomized meldable heap dễ triển khai và các hằng số trong giới hạn độ phức tạp đều nhỏ.
- Không yêu cầu duy trì điều kiện cân bằng và không cần thông tin vệ tinh (satellite information) trong các nút.
- Cuối cùng, cấu trúc này thể hiện hiệu suất thời gian trường hợp xấu tốt. Phần lớn thời gian thực thi của mỗi thao tác riêng lẻ là logarit với xác suất cao.
Skew Heap (Đồng loại nghiêng)
Skew heap (hay self-adjusting heap) là một cấu trúc dữ liệu heap được triển khai dưới dạng cây nhị phân.
Skew heap có lợi thế là có thể gộp (merge) nhanh hơn binary heap.
Khác với binary heap, không có ràng buộc cấu trúc, nên không đảm bảo chiều cao cây là logarit.
Chỉ cần thỏa mãn hai điều kiện:
- Thứ tự heap chung phải được duy trì (gốc là nhỏ nhất và đệ quy đúng cho các cây con), nhưng tính chất cân bằng (tất cả cấp độ phải đầy trừ cấp cuối) không cần thiết.
- Thao tác chính trong Skew Heap chỉ là Merge. Các thao tác khác như insert, extractMin() có thể triển khai chỉ dựa trên Merge.
Ví dụ minh họa
Cho skew heap 1:
Heap thứ hai:
Kết quả gộp:
Quy trình Merge đệ quy
merge(a1, a2)
Cho a1, a2 là hai min skew heap cần gộp.
Cho gốc a1 nhỏ hơn gốc a2 (nếu không, đổi chỗ).
Hoán đổi a1->left và a1->right.
a1->left = merge(a2, a1->left)