เพียริงฮีปและคิวอันดับ (Priority Queue)
เพียริงฮีป (Pairing Heaps) ถูกนำมาใช้เพื่อการทำงานที่สมบูรณ์แบบของ คิวอันดับ (Priority Queue) คิวอันดับติดตามค่าต่ำสุดของชุดวัตถุ ทุกครั้งที่นำสิ่งของออกจากคิว จะได้ค่าต่ำสุดเสมอ คิวอันดับมักถูกใช้เมื่อนำ อัลกอริทึมของดิกสตรา (Dijkstra's Algorithm) ไปคำนวณเส้นทางสั้นที่สุดในกราฟ
ทำไมเพียริงฮีปจึง "สมบูรณ์แบบ"
- เขียนโค้ดง่าย – โครงสร้างและการดำเนินการเข้าใจง่าย
- ทำงานดีในแอปพลิเคชันจริง – มีประสิทธิภาพสูงในการใช้งานจริง
- เวลาแบบแอมอร์ไทซ์ (Amortized Time) ดีเยี่ยม – แม้การดำเนินการแต่ละครั้งอาจใช้เวลานาน แต่ผลรวมตลอดวงจรชีวิตของคิวจะรวดเร็ว
- ดีกว่าฟีโบนัชชีฮีปในหลายกรณี – เขียนง่ายกว่าและมักทำงานได้ดีกว่า
คุณสมบัติพื้นฐานของเพียริงฮีป
แต่ละฮีปเชื่อมโยงกับวัตถุหรือค่า และมีชุดของ ฮีปย่อย (child heaps) ค่าของวัตถุจะมากกว่า (หรือน้อยกว่า) ค่าของฮีปย่อยเสมอ (ขึ้นอยู่กับ min-heap หรือ max-heap)
การดำเนินการพื้นฐาน
min(heap) – หาค่าต่ำสุด
ฟังก์ชันนี้ง่ายมาก เพียงดูค่าที่อยู่บนสุด (root) ของฮีป
merge(heap1, heap2) – รวมฮีปสองตัว
นำฮีปที่มีค่ามากกว่าไปเป็นลูกของฮีปอีกตัว ฟังก์ชันนี้ทำงานได้รวดเร็ว
