Nhóm kép
Sự tồn tại của các phương pháp chung để đạt được cấu trúc dữ liệu DEPQ (Hàng đợi ưu tiên kết thúc kép) hiệu quả từ cấu trúc dữ liệu hàng đợi ưu tiên một đầu (PQ) cũng cung cấp triển khai hiệu quả hoạt động loại bỏ (aNode) (hoạt động này loại bỏ aNode nút khỏi PQ). Phương pháp đơn giản nhất trong số các phương pháp này, phương pháp cấu trúc kép, theo dõi cả PQ tối thiểu và PQ tối đa của tất cả các phần tử DEPQ được liên kết với các con trỏ tương ứng giữa các nút của PQ tối thiểu và PQ tối đa bao gồm cùng một phần tử.
Hình A hiển thị cấu trúc đống kép cho các phần tử 7, 8, 3, 6, 5. Con trỏ tương ứng được hiển thị dưới dạng mũi tên màu đỏ.
Hình A:Kép heap
Mặc dù hình vẽ hiển thị từng phần tử được lưu trữ trong cả heap tối thiểu và tối đa, nó được yêu cầu lưu trữ từng phần tử chỉ trong một trong hai heap.
Các phép toán isEmpty và size được áp dụng bằng cách triển khai một kích thước thay đổi để theo dõi số lượng phần tử trong DEPQ. Phần tử tối thiểu nằm ở gốc của đống tối thiểu và phần tử tối đa nằm ở gốc của đống tối đa. Để chèn một phần tử A, chúng tôi chèn A vào cả vùng tối thiểu và tối đa, sau đó thiết lập các con trỏ tương ứng giữa các vị trí của A trong vùng tối thiểu và tối đa. Để loại bỏ phần tử tối thiểu, chúng tôi thực hiện removeMin từ min heap và remove (aNode), trong đó aNode là nút tương ứng cho phần tử bị loại bỏ, khỏi đống tối đa. Phần tử tối đa bị loại bỏ theo cách tương tự.
Tổng và lá thư
Tổng và lá thư là những kỹ thuật thư tín phức tạp hơn. Trong cả hai kỹ thuật này, một nửa phần tử nằm ở PQ tối thiểu và nửa còn lại ở PQ tối đa. Khi số phần tử là số lẻ, một phần tử được lưu trong bộ đệm. Phần tử được đệm này không phải là thành viên của một trong hai PQ. Trong kỹ thuật tương ứng tổng, mỗi phần tử x trong PQ tối thiểu được ghép nối với một phần tử riêng biệt y của PQ tối đa. (x, y) là một cặp phần tử tương ứng sao cho ưu tiên (x) <=priority (y).
Hình B hiển thị tổng số đống tương ứng cho 11 phần tử 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11. Phần tử 10 nằm trong bộ đệm. Các cặp tương ứng được hiển thị bằng các mũi tên màu đỏ.
Hình B:Tổng đống thư từ
Trong kỹ thuật tương ứng lá, mỗi phần tử lá của PQ tối thiểu và tối đa là một phần của một cặp tương ứng. Các phần tử nonleaf không yêu cầu phải nằm trong bất kỳ cặp nào tương ứng. Hình C hiển thị một đống tương ứng lá.
Hình C:Một đống thư từ trên lá
Cấu trúc tương ứng tổng và lá cần ít không gian hơn cấu trúc kép. Tuy nhiên, các Thuật toán DEPQ cho cấu trúc tương ứng tổng và lá phức tạp hơn các thuật toán cho cấu trúc kép. Trong số ba kỹ thuật thư từ, thư từ dạng lá là cấu trúc thư tín DEPQ nhanh nhất.
Thực hiện bất kỳ kỹ thuật tương ứng nào được mô tả, chúng ta có thể đến các cấu trúc DEPQ từ các đống, các cây cánh tả phân biệt chiều cao và các đống ghép nối. Trong các cấu trúc DEQP này, các hoạt động đặt (x), removeMin () và removeMax () tiêu tốn thời gian O (log n) (n là số phần tử trong DEPQ, để ghép nối các đống, đây là độ phức tạp được khấu hao) và các hoạt động DEPQ còn lại tiêu tốn O (1) thời gian.