Computer >> Máy Tính >  >> Lập trình >> Lập trình

DEPQ có thể hàn được

  • DEPQ có thể hàn (MDEPQ) được định nghĩa là DEPQ (Hàng đợi ưu tiên kết thúc kép), ngoài các thao tác DEPQ được liệt kê ở trên, bao gồm thao tác meld (p, q) ... kết hợp các DEPQ p và q thành một DEPQ duy nhất. Kết quả của việc ghép các hàng đợi ưu tiên kết thúc kép p và q là một hàng đợi ưu tiên kết thúc kép chứa tất cả các phần tử của p và q. Hoạt động meld phá hủy ở chỗ sau meld, p và q không còn là các DEPQ độc lập.
  • Để kết hợp hai DEPQ trong thời gian ngắn hơn tuyến tính, các DEPQ cần được biểu diễn bằng cách triển khai các con trỏ rõ ràng (thay vì các con trỏ ngầm như trong biểu diễn mảng của một đống) vì nếu không thì một số tuyến tính các phần tử cần được di chuyển từ ban đầu của họ đến các vị trí cuối cùng của họ.
  • Có thể chỉ ra rằng khi đống cặp tối thiểu-tối đa được biểu diễn theo cách như vậy, một phần tử (kích thước n) DEPQ có thể được kết hợp với một phần tử khác (kích thước k) (trong đó k <=n) trong O (log (n / k) * log k) thời gian.
  • Có thể chỉ ra rằng độ phức tạp của việc ghép hai đống tối thiểu-tối đa có kích thước tương ứng là a và b là Ω (a + b).
  • Một triển khai MDEPQ cho phép một người tính toán các phần tử tối thiểu và tối đa, chèn một phần tử và kết hợp hai hàng đợi ưu tiên trong thời gian O (1). Thời gian cần thiết để xóa phần tử tối thiểu hoặc tối đa là O (log n).
  • Có thể chỉ ra rằng cây cánh tả có thể được điều chỉnh để có được một biểu diễn đơn giản cho MDEPQ trong đó meld tiêu tốn thời gian logarit và các hoạt động còn lại có cùng độ phức tạp tiệm cận như khi bất kỳ biểu diễn DEPQ nào đã nói ở trên được triển khai.
  • Điều thú vị cần lưu ý là nếu chúng tôi triển khai cấu trúc FMPQ (Hàng đợi ưu tiên có thể hàn nhanh) làm cấu trúc MPQ cơ sở, chúng tôi sẽ có được cấu trúc MDEPQ tổng tương ứng trong đó removeMax và removeMin tiêu tốn thời gian logarit và các hoạt động còn lại sử dụng không đổi thời gian. Sự thích ứng này là tuyệt vời khi so sánh với sự thích ứng hàng đợi ưu tiên kép vì các yêu cầu về không gian gần như là một nửa. Ngoài ra, thích ứng toàn bộ thư tín nhanh hơn so với thích ứng hàng đợi ưu tiên kép.