นิยามเพียริงฮีป
เพียริงฮีป (Pairing Heap) สามารถเป็นได้สองแบบ:
- ฮีปว่าง (Empty Heap)
- เพียริงทรี (Pairing Tree) – ประกอบด้วยรูท (root element) และรายการของเพียริงทรีที่อาจว่างได้
คุณสมบัติการจัดลำดับฮีป
พาเรนต์ของโหนดใดๆ ต้องมีค่าไม่มากกว่าโหนดนั้นเอง (สำหรับ min-heap)
การนำเสนอแบบฟังก์ชันนิยม (Functional Representation)
type PairingTree[Element] = Heap(element: Element, subheaps: List[PairingTree[Element]]) type PairingHeap[Element] = Empty | PairingTree[Element]
สองประเภทหลัก
- Min Pairing Heaps – ใช้แทน Min Priority Queue
- Max Pairing Heaps – ใช้แทน Max Priority Queue
ในบทนี้เน้น Max Pairing Heaps ส่วน Min Pairing Heaps สามารถเปรียบเทียบได้โดยตรง
Max Pairing Heap คือ Max Tree
Max Pairing Heap นิยามได้อย่างง่ายว่าเป็น Max Tree โดยไม่จำเป็นต้องเป็น Binary Tree
ตัวอย่างภาพ
รูปแสดง Max Pairing Heaps 4 ตัว สังเกตว่าไม่จำเป็นต้องเป็น Binary Tree
