คิวลำดับความสำคัญที่หลอมได้
คำจำกัดความ
ฮีป Meldable แบบสุ่ม (เช่น Meldable Heap หรือ Randomized Meldable Priority Queue) ถูกกำหนดให้เป็นโครงสร้างข้อมูลตามคิวที่มีลำดับความสำคัญ ซึ่งโครงสร้างพื้นฐานยังเป็นทรีไบนารีที่เรียงลำดับฮีปด้วย อย่างไรก็ตาม ไม่มีกฎเกณฑ์ที่ยากและรวดเร็วเกี่ยวกับรูปร่างของไบนารีทรีพื้นฐาน
ข้อดี
- แนวทางนี้มีสิ่งอำนวยความสะดวกหลายอย่าง เช่น ได้เปรียบเหนือโครงสร้างข้อมูลที่คล้ายกัน
- มีวิธีการที่ง่ายกว่าโครงสร้างข้อมูลอื่นๆ
- การดำเนินการทั้งหมดสำหรับฮีปที่หลอมได้แบบสุ่มนั้นนำไปใช้ได้ง่าย และปัจจัยคงที่ในขอบเขตความซับซ้อนนั้นมีขนาดเล็ก
- นอกจากนี้ยังไม่มีข้อกำหนดในการรักษาสภาวะสมดุลและไม่จำเป็นต้องมีข้อมูลดาวเทียมภายในโหนด
- สุดท้าย โครงสร้างนี้แสดงให้เห็นถึงประสิทธิภาพของเวลาที่แย่ที่สุด ส่วนใหญ่เวลาดำเนินการของการดำเนินการแต่ละรายการจะเป็นแบบลอการิทึมที่มีความน่าจะเป็นสูง
กองเอียง
skew heap (หรือ self – adjustment heap) ถูกกำหนดให้เป็นโครงสร้างข้อมูลของ heap ที่นำไปใช้เป็นไบนารีทรี
Skew heaps มีประโยชน์เพราะสามารถรวมได้เร็วกว่าไบนารี heaps
ต่างจากไบนารีฮีปตรงที่ไม่มีข้อจำกัดด้านโครงสร้าง ดังนั้นจึงไม่มีการรับประกันว่าความสูงของต้นไม้จะเป็นแบบลอการิทึม
ต้องเป็นไปตามเงื่อนไขสองข้อเท่านั้น -
- ต้องรักษาลำดับฮีปทั่วไปไว้ที่นั่น (รูตมีค่าน้อยที่สุดและเหมือนกันกับทรีย่อยแบบเรียกซ้ำ) แต่คุณสมบัติที่สมดุล (ทุกระดับต้องเต็มยกเว้นสุดท้าย) ไม่จำเป็น
- การทำงานหลักใน Skew Heaps เป็นเพียงการผสาน เราสามารถใช้การดำเนินการอื่น ๆ เช่น insert, extractMin() ฯลฯ ที่เกี่ยวข้องกับ Merge เท่านั้น
ตัวอย่าง
ให้เบ้ฮีป 1 เป็น
ฮีปที่สองที่จะสมมติขึ้น
และเราได้ต้นไม้ที่ผสานสุดท้ายในรูปแบบของ
กระบวนการผสานแบบเรียกซ้ำ
ผสาน (a1, a2) ให้ a1 และ a2 เป็นฮีปเอียงสองนาทีที่จะถูกรวม ให้รูทของ a1 เล็กกว่ารูทของ a2 (ถ้าไม่เล็กกว่า เราก็สลับกันได้) เราสลับ a1->left และ a1->right.a1->left =merge (a2, a1->left)
