Computer >> คอมพิวเตอร์ >  >> การเขียนโปรแกรม >> การเขียนโปรแกรม

โครงสร้างข้อมูลตามการโต้ตอบ


การโต้ตอบแบบรวมและแบบใบไม้เป็นเทคนิคการโต้ตอบที่ซับซ้อนกว่า ในเทคนิคทั้งสองนี้ ครึ่งหนึ่งขององค์ประกอบจะอยู่ที่ PQ ขั้นต่ำ และอีกครึ่งหนึ่งอยู่ใน PQ สูงสุด เมื่อจำนวนองค์ประกอบเป็นเลขคี่ องค์ประกอบหนึ่งจะถูกเก็บไว้ในบัฟเฟอร์ อิลิเมนต์บัฟเฟอร์นี้ไม่ใช่สมาชิกของ PQ ในเทคนิคการโต้ตอบทั้งหมด แต่ละองค์ประกอบ x ใน PQ ขั้นต่ำจะจับคู่กับองค์ประกอบ y ที่แตกต่างกันของ PQ สูงสุด (x, y) เป็นคู่ขององค์ประกอบที่สอดคล้องกันเช่นที่ priority(x) <=priority(y)

รูปที่ E แสดงฮีปการติดต่อทั้งหมดสำหรับ 11 องค์ประกอบ 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 องค์ประกอบ 10 อยู่ในบัฟเฟอร์ คู่ที่ตรงกันจะแสดงด้วยลูกศรสีแดง

โครงสร้างข้อมูลตามการโต้ตอบ

รูป E:กองการโต้ตอบทั้งหมด

ในเทคนิคการโต้ตอบของใบไม้ แต่ละองค์ประกอบใบไม้ของ PQ ขั้นต่ำและสูงสุดจำเป็นต้องเป็นส่วนหนึ่งของคู่ที่สอดคล้องกัน องค์ประกอบที่ไม่ใช่ใบไม้ไม่จำเป็นต้องอยู่ในคู่ที่สอดคล้องกัน รูปที่ F แสดงกองจดหมายโต้ตอบใบไม้

โครงสร้างข้อมูลตามการโต้ตอบ

รูปที่ F:กองจดหมายโต้ตอบใบไม้

โครงสร้างการโต้ตอบทั้งหมดและใบไม้ต้องการพื้นที่น้อยกว่าโครงสร้างคู่ อย่างไรก็ตาม อัลกอริธึม DEPQ สำหรับโครงสร้างการติดต่อแบบรวมและแบบลีฟนั้นซับซ้อนกว่าสำหรับโครงสร้างแบบคู่ ในบรรดาเทคนิคการโต้ตอบทั้งสามแบบ การโต้ตอบแบบใบไม้เป็นโครงสร้างการโต้ตอบของ DEPQ ที่เร็วที่สุด