Hàng đợi ưu tiên có thể hàn
Định nghĩa
Một đống ngẫu nhiên có thể sử dụng được (còn Meldable Heap hoặc Randomized Meldable Priority Queue) được định nghĩa là một cấu trúc dữ liệu dựa trên hàng đợi ưu tiên, trong đó cấu trúc bên dưới cũng là một cây nhị phân có thứ tự đống. Tuy nhiên, không có quy tắc cứng và nhanh nào 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ó một số tiện ích, tức là lợi thế hơn các cấu trúc dữ liệu tương tự.
- Nó 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ả các hoạt động cho đống ngẫu nhiên có thể kết hợp đều dễ áp dụng và các yếu tố không đổi trong giới hạn phức tạp của chúng là nhỏ.
- Cũng không có yêu cầu để duy trì các điều kiện cân bằng và không cần thông tin vệ tinh trong các nút.
- Cuối cùng, cấu trúc này thể hiện hiệu quả thời gian tốt trong trường hợp xấu nhất. Phần lớn thời gian thực hiện của từng thao tác riêng lẻ là lôgarit với xác suất cao.
Hàng chồng xiên
Một heap lệch (hoặc heap tự điều chỉnh) được định nghĩa là 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 vì chúng có thể hợp nhất nhanh hơn so với binary heap.
Không giống như đống nhị phân, không có ràng buộc về cấu trúc, vì vậy không có gì đảm bảo rằng chiều cao của cây là logarit.
Chỉ cần thỏa mãn hai điều kiện -
- Thứ tự đống chung phải được duy trì ở đó (gốc là tối thiểu và điều này cũng đúng một cách đệ quy cho các cây con), nhưng thuộc tính cân bằng (tất cả các cấp phải đầy đủ ngoại trừ cấp cuối cùng) là không cần thiết.
- Hoạt động chính trong Skew Heaps chỉ là Hợp nhất. Chúng tôi có thể triển khai các hoạt động khác như insert, extractMin (), v.v. được liên kết với Merge chỉ.
Ví dụ
Để cho đống xiên 1 là
Đống thứ hai được giả định
Và chúng tôi có được cây hợp nhất cuối cùng ở dạng
Quy trình hợp nhất đệ quy
merge (a1, a2) Gọi a1 và a2 là hai heap xiên nhỏ nhất sẽ được hợp nhất. Đặt gốc của a1 nhỏ hơn gốc của a2 (Nếu không nhỏ hơn, chúng ta có thể hoán đổi để nhận được cùng) Chúng ta hoán đổi a1-> left và a1-> right.a1-> left =merge (a2, a1-> left)