Heap đôi (Dual Heap)
Tồn tại các phương pháp chung để đạt được cấu trúc dữ liệu DEPQ (Double Ended Priority Queue) hiệu quả từ cấu trúc dữ liệu hàng đợi ưu tiên đơn đầu (single-ended priority queue - PQ) cũng cung cấp cài đặt hiệu quả cho thao tác remove(aNode) (loại bỏ nút aNode khỏi PQ). Phương pháp đơn giản nhất, phương pháp cấu trúc đôi (dual structure method), theo dõi cả min PQ và max PQ của tất cả phần tử DEPQ cùng con trỏ tương ứng giữa nút min PQ và max PQ chứa cùng phần tử.
Hình A hiển thị cấu trúc heap đôi cho phần tử 7, 8, 3, 6, 5. Con trỏ tương ứng hiển thị bằng mũi tên đỏ.
Hình A: Heap đôi
Mặc dù hình vẽ hiển thị mỗi phần tử lưu trong cả min và max heap, nhưng yêu cầu chỉ lưu mỗi phần tử trong một trong hai heap.
Thao tác isEmpty và size dùng biến size theo dõi số phần tử DEPQ. Phần tử nhỏ nhất ở gốc min heap, lớn nhất ở gốc max heap. Để chèn A, chèn A vào cả min và max heap, thiết lập con trỏ tương ứng. Để xóa min, làm removeMin từ min heap và remove(aNode) từ max heap, aNode là nút tương ứng. Xóa max tương tự.
Tương ứng toàn phần và lá (Total and leaf correspondence)
Tương ứng toàn phần và lá là kỹ thuật tương ứng tinh vi hơn. Cả hai kỹ thuật: nửa phần tử trong min PQ, nửa kia trong max PQ. Số phần tử lẻ → một phần tử trong buffer (không thuộc PQ nào). Tương ứng toàn phần: mỗi x trong min PQ ghép với y riêng biệt trong max PQ, priority(x) ≤ priority(y).
Hình B hiển thị heap tương ứng toàn phần cho 11 phần tử 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11. Phần tử 10 trong buffer. Cặp tương ứng bằng mũi tên đỏ.
Hình B: Heap tương ứng toàn phần
Tương ứng lá: mỗi phần tử lá của min và max PQ phải là cặp tương ứng. Phần tử không phải lá không cần. Hình C hiển thị heap tương ứng lá.
Hình C: Heap tương ứng lá
Cấu trúc tương ứng toàn phần và lá cần không gian ít hơn cấu trúc đôi. Tuy nhiên, thuật toán DEPQ cho chúng phức tạp hơn cấu trúc đôi. Trong ba kỹ thuật, tương ứng lá là cấu trúc DEPQ tương ứng nhanh nhất.
Áp dụng bất kỳ kỹ thuật tương ứng nào mô tả, ta có được cấu trúc DEPQ từ heap, cây leftist lệch chiều cao (height biased leftist trees), và pairing heap. Trong các cấu trúc DEQP này, thao tác put(x), removeMin(), removeMax() tốn O(log n) (n số phần tử DEPQ, đối với pairing heap là khấu hao), các thao tác DEPQ còn lại O(1).