Hàng đợi ưu tiên kết thúc kép (DEPQ) hoặc heap kết thúc kép được định nghĩa là cấu trúc dữ liệu giống như hàng đợi hoặc đống ưu tiên, nhưng cho phép loại bỏ hiệu quả cả giá trị tối đa và tối thiểu, theo một số thứ tự trên các khóa hoặc mục được lưu trữ trong cấu trúc. Mọi phần tử trong DEPQ được liên kết với một mức độ ưu tiên hoặc giá trị. Trong một DEPQ, có thể loại bỏ hoặc loại bỏ các phần tử theo cả thứ tự tăng dần và giảm dần.
Hoạt động
Hàng đợi ưu tiên kết thúc kép bao gồm các hoạt động sau
isEmpty ()
Hàm này có nhiệm vụ kiểm tra xem DEPQ có trống không và trả về true nếu trống.
kích thước ()
Hàm này chịu trách nhiệm trả về tổng số phần tử có trong DEPQ.
getMin (y)
Hàm này chịu trách nhiệm trả về phần tử y có mức ưu tiên ít nhất.
getMax (y)
Hàm này chịu trách nhiệm trả về phần tử y có mức ưu tiên cao nhất.
đặt (y)
Hàm này có nhiệm vụ chèn phần tử y vào DEPQ.
removeMin (y)
Hàm này có nhiệm vụ xóa một phần tử y với mức ưu tiên tối thiểu và trả về phần tử này.
removeMax (y)
Hàm này chịu trách nhiệm loại bỏ một phần tử y có mức ưu tiên tối đa và trả về phần tử này.
Thực hiện
Hàng đợi ưu tiên kết thúc kép có thể được xây dựng hoặc hình thành từ cây tìm kiếm nhị phân cân bằng (trong đó các phần tử nhỏ nhất và lớn nhất được coi là các lá ngoài cùng bên trái và ngoài cùng bên phải tương ứng) hoặc triển khai các cấu trúc dữ liệu chuyên biệt như min-max heap và ghép nối heap.
Các phương pháp chung để đến hàng đợi ưu tiên kết thúc kép từ hàng đợi ưu tiên bình thường là:
Phương pháp cấu trúc kép
Theo phương pháp này, hai hàng đợi ưu tiên khác nhau cho min và max được thiết lập hoặc duy trì. Các phần tử giống nhau trong cả hai hàng đợi ưu tiên được hiển thị hoặc hiển thị với sự trợ giúp của con trỏ tương ứng.
Ở đây, các phần tử tối thiểu và tối đa được biểu thị là các giá trị chứa trong các nút gốc của min heap và max heap tương ứng.
Xóa phần tử min - Hoạt động removemin () trên đống tối thiểu và loại bỏ (giá trị nút) trên đống tối đa, trong đó giá trị nút được xác định là giá trị trong nút tương ứng trong đống tối đa.
Xóa phần tử tối đa - Hoạt động removemax () trên đống tối đa và loại bỏ (giá trị nút) trên đống nhỏ nhất, trong đó giá trị nút được xác định là giá trị trong nút tương ứng trong đống tối thiểu.
Tổng số thư từ
Một nửa các phần tử nằm trong hàng đợi ưu tiên tối thiểu và nửa còn lại trong hàng đợi ưu tiên tối đa. Mỗi phần tử trong hàng đợi ưu tiên tối thiểu có sự tương ứng 1-1 với một phần tử trong hàng ưu tiên tối đa. Nếu số phần tử trong DEPQ chỉ ra giá trị lẻ, thì một trong các phần tử được giữ lại trong bộ đệm, tức là một vùng lưu trữ cụ thể. Mức độ ưu tiên của mọi phần tử trong hàng đợi ưu tiên tối thiểu sẽ nhỏ hơn hoặc bằng phần tử tương ứng trong hàng đợi ưu tiên tối đa.
Lá thư
Theo phương pháp này, chỉ các phần tử lá của hàng đợi ưu tiên tối thiểu và tối đa tạo thành các cặp một-một tương ứng. Không bắt buộc các phần tử không phải lá phải nằm trong cặp tương ứng một đối một.
Các đống khoảng thời gian
Bên cạnh các phương pháp thư từ được đề cập ở trên, DEPQ có thể đạt được việc triển khai các đống khoảng thời gian một cách hoàn hảo. Một heap khoảng giống như một heap min-max được nhúng trong đó mỗi nút bao gồm hai phần tử. Nó được định nghĩa là một cây nhị phân hoàn chỉnh trong đó -
- Phần tử bên trái luôn nhỏ hơn hoặc bằng phần tử bên phải.
- Cả hai phần tử đều xác định hoặc chỉ định một khoảng thời gian đóng.
- Khoảng thời gian được biểu diễn bởi bất kỳ nút nào ngoại trừ nút gốc được biểu thị là khoảng thời gian con của nút mẹ.
- Các phần tử ở phía bên trái xác định hoặc biểu thị một đống tối thiểu.
- Các phần tử ở phía bên phải xác định hoặc biểu thị một đống tối đa.