ฮีปคู่
การมีอยู่ของวิธีการทั่วไปที่จะมาถึงโครงสร้างข้อมูล DEPQ (Double Ended Priority Queue) ที่มีประสิทธิภาพจากโครงสร้างข้อมูล single-ended Priority Queue (PQ) ที่ให้การนำการดำเนินการ Remove (aNode) ไปใช้อย่างมีประสิทธิภาพ (การดำเนินการนี้จะกำจัดโหนด aNode จาก ป.ป.ช.) วิธีที่ง่ายที่สุดของวิธีเหล่านี้ วิธีโครงสร้างแบบคู่ ติดตามทั้ง PQ ขั้นต่ำและ PQ สูงสุดขององค์ประกอบ DEPQ ทั้งหมดที่เกี่ยวข้องกับตัวชี้การติดต่อระหว่างโหนดของ PQ ขั้นต่ำและ PQ สูงสุดที่ประกอบด้วยองค์ประกอบเดียวกัน
รูปที่ A แสดงโครงสร้างแบบ dual heap สำหรับองค์ประกอบ 7, 8, 3, 6, 5 ตัวชี้การโต้ตอบจะแสดงเป็นลูกศรสีแดง
รูป A:Dual heap
แม้ว่ารูปจะแสดงแต่ละองค์ประกอบที่จัดเก็บไว้ในฮีปขั้นต่ำและสูงสุด แต่ก็จำเป็นต้องเก็บแต่ละองค์ประกอบไว้ในฮีปหนึ่งในสองฮีปเท่านั้น
การดำเนินการ isEmpty และ size ถูกนำไปใช้โดยการใช้ขนาดตัวแปรที่ติดตามจำนวนองค์ประกอบใน DEPQ อิลิเมนต์ต่ำสุดจะอยู่ที่รูทของฮีปขั้นต่ำ และอิลิเมนต์สูงสุดจะอยู่ที่รูทของฮีปสูงสุด ในการแทรกองค์ประกอบ A เราแทรก A ลงในฮีปขั้นต่ำและสูงสุด จากนั้นตั้งค่าพอยน์เตอร์การโต้ตอบระหว่างตำแหน่งของ A ในฮีปขั้นต่ำและสูงสุด ในการกำจัดองค์ประกอบขั้นต่ำ เราทำ RemoveMin จากฮีปขั้นต่ำและการลบ (aNode) โดยที่ aNode เป็นโหนดที่สอดคล้องกันสำหรับองค์ประกอบที่ถูกลบออกจากฮีปสูงสุด องค์ประกอบสูงสุดจะถูกกำจัดในลักษณะที่คล้ายคลึงกัน
การโต้ตอบทั้งหมดและใบไม้
การโต้ตอบแบบรวมและแบบใบไม้เป็นเทคนิคการโต้ตอบที่ซับซ้อนกว่า ในเทคนิคทั้งสองนี้ ครึ่งหนึ่งขององค์ประกอบจะอยู่ที่ PQ ขั้นต่ำ และอีกครึ่งหนึ่งอยู่ใน PQ สูงสุด เมื่อจำนวนองค์ประกอบเป็นเลขคี่ องค์ประกอบหนึ่งจะถูกเก็บไว้ในบัฟเฟอร์ อิลิเมนต์บัฟเฟอร์นี้ไม่ใช่สมาชิกของ PQ ในเทคนิคการโต้ตอบทั้งหมด แต่ละองค์ประกอบ x ใน PQ ขั้นต่ำจะจับคู่กับองค์ประกอบ y ที่แตกต่างกันของ PQ สูงสุด (x, y) เป็นคู่ขององค์ประกอบที่สอดคล้องกันเช่นที่ priority(x) <=priority(y)
รูปที่ B แสดงฮีปการติดต่อทั้งหมดสำหรับ 11 องค์ประกอบ 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 องค์ประกอบ 10 อยู่ในบัฟเฟอร์ คู่ที่ตรงกันจะแสดงด้วยลูกศรสีแดง
รูป B:กองการโต้ตอบทั้งหมด
ในเทคนิคการโต้ตอบของใบไม้ แต่ละองค์ประกอบใบไม้ของ PQ ขั้นต่ำและสูงสุดจำเป็นต้องเป็นส่วนหนึ่งของคู่ที่สอดคล้องกัน องค์ประกอบที่ไม่ใช่ใบไม้ไม่จำเป็นต้องอยู่ในคู่ที่สอดคล้องกัน รูป C แสดงกองจดหมายโต้ตอบใบไม้
รูป C:กองจดหมายโต้ตอบใบไม้
โครงสร้างการโต้ตอบทั้งหมดและใบไม้ต้องการพื้นที่น้อยกว่าโครงสร้างคู่ อย่างไรก็ตาม อัลกอริธึม DEPQ สำหรับโครงสร้างการติดต่อแบบรวมและแบบลีฟนั้นซับซ้อนกว่าสำหรับโครงสร้างแบบคู่ จากสามเทคนิคการโต้ตอบ การโต้ตอบแบบใบไม้เป็นโครงสร้างการโต้ตอบ DEPQ ที่เร็วที่สุด
การใช้เทคนิคการโต้ตอบที่อธิบายไว้ใด ๆ เราสามารถมาถึงโครงสร้าง DEPQ จากฮีป ต้นไม้ฝ่ายซ้ายที่มีอคติสูง และการจับคู่ฮีป ในโครงสร้าง DEQP เหล่านี้ การดำเนินการ put(x), removeMin() และ removeMax() ใช้เวลา O(log n) (n คือจำนวนขององค์ประกอบใน DEPQ สำหรับการจับคู่ฮีป นี่คือความซับซ้อนที่ตัดจำหน่าย) และ การดำเนินการ DEPQ ที่เหลือใช้เวลา O(1)
