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

คิวลำดับความสำคัญ Meldable และ Skew Heaps


คิวลำดับความสำคัญที่หลอมได้

คำจำกัดความ

ฮีป Meldable แบบสุ่ม (เช่น Meldable Heap หรือ Randomized Meldable Priority Queue) ถูกกำหนดให้เป็นโครงสร้างข้อมูลตามคิวที่มีลำดับความสำคัญ ซึ่งโครงสร้างพื้นฐานยังเป็นทรีไบนารีที่เรียงลำดับฮีปด้วย อย่างไรก็ตาม ไม่มีกฎเกณฑ์ที่ยากและรวดเร็วเกี่ยวกับรูปร่างของไบนารีทรีพื้นฐาน

ข้อดี

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

กองเอียง

skew heap (หรือ self – adjustment heap) ถูกกำหนดให้เป็นโครงสร้างข้อมูลของ heap ที่นำไปใช้เป็นไบนารีทรี

Skew heaps มีประโยชน์เพราะสามารถรวมได้เร็วกว่าไบนารี heaps

ต่างจากไบนารีฮีปตรงที่ไม่มีข้อจำกัดด้านโครงสร้าง ดังนั้นจึงไม่มีการรับประกันว่าความสูงของต้นไม้จะเป็นแบบลอการิทึม

ต้องเป็นไปตามเงื่อนไขสองข้อเท่านั้น -

  • ต้องรักษาลำดับฮีปทั่วไปไว้ที่นั่น (รูตมีค่าน้อยที่สุดและเหมือนกันกับทรีย่อยแบบเรียกซ้ำ) แต่คุณสมบัติที่สมดุล (ทุกระดับต้องเต็มยกเว้นสุดท้าย) ไม่จำเป็น
  • การทำงานหลักใน Skew Heaps เป็นเพียงการผสาน เราสามารถใช้การดำเนินการอื่น ๆ เช่น insert, extractMin() ฯลฯ ที่เกี่ยวข้องกับ Merge เท่านั้น

ตัวอย่าง

ให้เบ้ฮีป 1 เป็น

คิวลำดับความสำคัญ Meldable และ Skew Heaps

ฮีปที่สองที่จะสมมติขึ้น

คิวลำดับความสำคัญ Meldable และ Skew Heaps

และเราได้ต้นไม้ที่ผสานสุดท้ายในรูปแบบของ

คิวลำดับความสำคัญ Meldable และ Skew Heaps

กระบวนการผสานแบบเรียกซ้ำ

ผสาน (a1, a2) ให้ a1 และ a2 เป็นฮีปเอียงสองนาทีที่จะถูกรวม ให้รูทของ a1 เล็กกว่ารูทของ a2 (ถ้าไม่เล็กกว่า เราก็สลับกันได้) เราสลับ a1->left และ a1->right.a1->left =merge (a2, a1->left)