คืออะไร?
เพียริงฮีป (Pairing Heap) เป็นประเภทหนึ่งของโครงสร้างข้อมูลฮีป ที่มี การนำไปใช้งานที่ง่ายดาย และ ประสิทธิภาพแบบแอมอร์ไทซ์ที่ยอดเยี่ยมในทางปฏิบัติ
เพียริงฮีปเป็นโครงสร้างต้นไม้แบบหลายทาง (Multiway Tree) ที่จัดลำดับแบบฮีป สามารถมองว่าเป็น ฟีโบนัชชีฮีปที่ลดรูป (Simplified Fibonacci Heaps)
การประยุกต์ใช้
ถือเป็น "ตัวเลือกที่แข็งแกรบ" (Robust Choice) สำหรับการนำอัลกอริทึมอย่าง Prim's MST Algorithm ไปใช้งาน รองรับการดำเนินการต่อไปนี้ (สมมติเป็น min-heap):
- find-min – คืนค่าองค์ประกอบบนสุดของฮีป (Root)
- meld – เปรียบเทียบรูทสองตัว ตัวที่เล็กกว่าคงเป็นรูท ตัวที่ใหญ่กว่าและซับทรีกลายเป็นลูกของรูทนั้น
- insert – สร้างฮีปใหม่สำหรับองค์ประกอบที่แทรก แล้ว meld เข้ากับฮีปเดิม
- decrease-key (ตัวเลือก) – นำซับทรีที่รูทเป็นคีย์ที่จะลดออก แทนที่คีย์ด้วยค่าที่เล็กลง แล้ว meld กลับเข้าไป
- delete-min – นำรูทออก และทำ meld ซ้ำๆ ของซับทรีจนเหลือต้นไม้เดียว ใช้กลยุทธ์การรวมหลายแบบ
โครงสร้างโหนด
แต่ละโหนดมี pointer ชี้ไปยัง ลูกซ้าย (left child) และลูกซ้ายชี้ไปยัง พี่น้องถัดไป (next sibling)
ตัวอย่างภาพ
ความซับซ้อนของเวลา
การวิเคราะห์ความซับซ้อนเวลาของเพียริงฮีปได้แรงบันดาลใจหลักจาก Splay Trees
- delete-min: O(log n) แบบแอมอร์ไทซ์
- find-min, meld, insert: O(1) แบบแอมอร์ไทซ์
