Hàng đợi ưu tiên hai đầu (DEPQ) hoặc heap hai đầu (double-ended heap) được định nghĩa là cấu trúc dữ liệu giống hàng đợi ưu tiên (priority queue) hoặc heap, nhưng cho phép xóa hiệu quả cả phần tử lớn nhất và nhỏ nhất, theo thứ tự nào đó trên các khóa (keys) hoặc mục (items) lưu trong cấu trúc. Mọi phần tử trong DEPQ liên kết với một ưu tiên hoặc giá trị. Trong DEPQ, có thể loại bỏ phần tử theo thứ tự tăng dần và giảm dần.
Các thao tác (Operations)
Một hàng đợi ưu tiên hai đầu bao gồm các thao tác sau:
isEmpty() - Kiểm tra DEPQ rỗng, trả về true nếu rỗng.
size() - Trả về tổng số phần tử trong DEPQ.
getMin(y) - Trả về phần tử y có ưu tiên thấp nhất.
getMax(y) - Trả về phần tử y có ưu tiên cao nhất.
put(y) - Chèn phần tử y vào DEPQ.
removeMin(y) - Xóa và trả về phần tử y có ưu tiên nhỏ nhất.
removeMax(y) - Xóa và trả về phần tử y có ưu tiên lớn nhất.
Cài đặt (Implementation)
Hàng đợi ưu tiên hai đầu có thể xây dựng từ cây tìm kiếm nhị phân cân bằng (balanced binary search trees) (nơi phần tử nhỏ nhất và lớn nhất là lá trái nhất và phải nhất), hoặc dùng cấu trúc dữ liệu đặc biệt như min-max heap và pairing heap.
Các phương pháp chung để đạt DEPQ từ hàng đợi ưu tiên thông thường:
Phương pháp cấu trúc đôi (Dual structure method)
Theo phương pháp này, hai hàng đợi ưu tiên khác nhau cho min và max được duy trì. Các phần tử giống nhau trong cả hai hàng đợi được hiển thị bằng con trỏ tương ứng (correspondence pointers).
Ở đây, phần tử nhỏ nhất và lớn nhất là giá trị chứa trong nút gốc của min heap và max heap tương ứng.
Xóa phần tử min − Thực hiện removemin() trên min heap và remove(node value) trên max heap, nơi node value là giá trị trong nút tương ứng trong max heap.
Xóa phần tử max − Thực hiện removemax() trên max heap và remove(node value) trên min heap, nơi node value là giá trị trong nút tương ứng trong min heap.
Tương ứng toàn phần (Total correspondence)
Nửa phần tử ở min priority queue, nửa kia ở max priority queue. Mỗi phần tử trong min PQ có tương ứng một-một với phần tử trong max PQ. Nếu số phần tử DEPQ là lẻ, một phần tử được giữ trong buffer (vùng lưu trữ cụ thể). Ưu tiên mọi phần tử trong min PQ sẽ nhỏ hơn hoặc bằng phần tử tương ứng trong max PQ.
Tương ứng lá (Leaf correspondence)
Theo phương pháp này chỉ các phần tử lá của min và max priority queue tạo thành cặp tương ứng một-một. Không yêu cầu phần tử không phải lá phải ở trong cặp tương ứng một-một.
Heap khoảng (Interval heaps)
Ngoài các phương pháp tương ứng trên, DEPQ có thể đạt được hoàn hảo bằng heap khoảng. Interval heap giống như min-max heap nhúng mà mỗi nút chứa hai phần tử. Được định nghĩa là cây nhị phân hoàn chỉnh trong đó:
- Phần tử trái luôn nhỏ hơn hoặc bằng phần tử phải.
- Cả hai phần tử xác định một khoảng đóng.
- Khoảng biểu diễn bởi bất kỳ nút nào trừ gốc là khoảng con của nút cha.
- Phần tử bên trái tạo thành min heap.
- Phần tử bên phải tạo thành max heap.