คิวลำดับความสำคัญที่สิ้นสุดสองครั้ง (DEPQ)

double-ended priority queue (DEPQ) หรือ double-ended heap ถูกกำหนดให้เป็นโครงสร้างข้อมูล เช่น คิวลำดับความสำคัญหรือฮีป แต่อนุญาตให้ลบทั้งค่าสูงสุดและต่ำสุดอย่างมีประสิทธิภาพ ตามการเรียงลำดับคีย์หรือรายการที่จัดเก็บไว้ใน โครงสร้าง. ทุกองค์ประกอบใน DEPQ ที่เกี่ยวข้องกับลำดับความสำคัญหรือค่า ใน DEPQ เป็นไปได้ที่จะกำจัดหรือลบองค์ประกอบทั้งจากน้อยไปหามากและจากมากไปน้อย

ปฏิบัติการ

คิวลำดับความสำคัญแบบดับเบิ้ลเอนด์ประกอบด้วยการดำเนินการดังต่อไปนี้

isEmpty()

ฟังก์ชันนี้มีหน้าที่ตรวจสอบว่า DEPQ ว่างเปล่าและคืนค่าเป็น จริง หากว่างเปล่า

ขนาด()

ฟังก์ชันนี้มีหน้าที่ส่งคืนจำนวนองค์ประกอบทั้งหมดที่มีอยู่ใน DEPQ

getMin(y)

ฟังก์ชันนี้มีหน้าที่ส่งคืนองค์ประกอบ y ที่มีลำดับความสำคัญน้อยที่สุด

getMax(y)

ฟังก์ชันนี้มีหน้าที่ส่งคืนองค์ประกอบ y ที่มีลำดับความสำคัญสูงสุด

ใส่(y)

ฟังก์ชันนี้มีหน้าที่ในการแทรกองค์ประกอบ y ใน DEPQ

ลบMin(y)

ฟังก์ชันนี้มีหน้าที่ลบองค์ประกอบ y ที่มีลำดับความสำคัญขั้นต่ำและส่งคืนองค์ประกอบนี้

removeMax(y)

ฟังก์ชันนี้มีหน้าที่ลบองค์ประกอบ y ที่มีลำดับความสำคัญสูงสุดและส่งคืนองค์ประกอบนี้

การนำไปใช้

คิวลำดับความสำคัญแบบดับเบิ้ลเอนด์สามารถสร้างหรือสร้างจากทรีการค้นหาแบบไบนารีที่สมดุลได้ (โดยที่องค์ประกอบที่เล็กที่สุดและใหญ่ที่สุดจะถือว่าเป็นการออกจากซ้ายสุดและขวาสุดตามลำดับ) หรือใช้โครงสร้างข้อมูลพิเศษ เช่น ฮีปต่ำสุด-สูงสุด และฮีปการจับคู่

วิธีการทั่วไปในการมาถึงคิวลำดับความสำคัญแบบ double-ended จากคิวที่มีลำดับความสำคัญปกติคือ:

วิธีโครงสร้างคู่

ตามวิธีการนี้ มีการตั้งค่าหรือรักษาคิวลำดับความสำคัญที่แตกต่างกันสองรายการสำหรับค่าต่ำสุดและสูงสุด องค์ประกอบเดียวกันในคิวลำดับความสำคัญทั้งสองจะแสดงหรือแสดงโดยใช้ตัวชี้การติดต่อ

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

การลบองค์ประกอบขั้นต่ำ - ดำเนินการ removemin() บนฮีปขั้นต่ำและลบ (ค่าโหนด) บนฮีปสูงสุด โดยที่ค่าโหนดถูกกำหนดเป็นค่าในโหนดที่เกี่ยวข้องในฮีปสูงสุด

การลบองค์ประกอบสูงสุด ดำเนินการ removemax() บนฮีปสูงสุดและลบ (ค่าโหนด) บนฮีปขั้นต่ำ โดยที่ค่าโหนดถูกกำหนดเป็นค่าในโหนดที่เกี่ยวข้องในฮีปขั้นต่ำ

จำนวนการติดต่อทั้งหมด

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

ใบโต้ตอบ

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

ช่วงฮีป

นอกจากวิธีการโต้ตอบที่กล่าวถึงข้างต้นแล้ว สามารถรับ DEPQ ได้โดยใช้ช่วงฮีปอย่างสมบูรณ์แบบ ฮีปช่วงเวลาเปรียบเสมือนฮีปต่ำสุด-สูงสุดที่ฝังอยู่ ซึ่งแต่ละโหนดประกอบด้วยสององค์ประกอบ มันถูกกำหนดให้เป็นต้นไม้ไบนารีที่สมบูรณ์ซึ่ง -

• องค์ประกอบด้านซ้ายจะน้อยกว่าหรือเท่ากับองค์ประกอบที่ถูกต้องเสมอ
• ทั้งสององค์ประกอบกำหนดหรือระบุช่วงปิด
• ช่วงเวลาที่แสดงโดยโหนดใดๆ ยกเว้น root จะแสดงเป็นช่วงเวลาย่อยของโหนดหลัก
• องค์ประกอบทางด้านซ้ายมือกำหนดหรือแสดงถึงฮีปขั้นต่ำ
• องค์ประกอบทางด้านขวามือกำหนดหรือแสดงถึงฮีปสูงสุด