การจับคู่ฮีปถูกกำหนดให้เป็นประเภทของโครงสร้างข้อมูลฮีปที่มีการนำไปใช้งานที่ค่อนข้างง่ายและประสิทธิภาพการตัดจำหน่ายที่ใช้งานได้จริงที่ยอดเยี่ยม
การจับคู่ฮีปเป็นโครงสร้างแบบหลายทางที่เรียงลำดับฮีป และสามารถแสดงเป็นฮีป Fibonacci แบบง่ายได้
สิ่งเหล่านี้ถือเป็น "ตัวเลือกที่แข็งแกร่ง" สำหรับการนำอัลกอริธึมดังกล่าวไปใช้ เช่น อัลกอริธึม MST ของ Prim และสนับสนุนการดำเนินการต่อไปนี้ (สมมติว่าเป็นฮีปขั้นต่ำ) –
- ค้นหานาที − ฟังก์ชันนี้มีหน้าที่ส่งคืนองค์ประกอบด้านบนของฮีป
- หลอมรวม ฟังก์ชันนี้มีหน้าที่เปรียบเทียบองค์ประกอบรูททั้งสององค์ประกอบ ยิ่งรากของผลลัพธ์เล็กลงเท่าใด องค์ประกอบที่ใหญ่กว่าและทรีย่อยขององค์ประกอบจะถูกเพิ่มเป็นลูกของรูทนี้
- แทรก − ฟังก์ชันนี้มีหน้าที่สร้างฮีปใหม่สำหรับองค์ประกอบที่แทรกและรวมเข้ากับฮีปดั้งเดิม
- คีย์ลด (ไม่บังคับ) − ฟังก์ชันนี้มีหน้าที่ลบทรีย่อยที่รูทที่คีย์เพื่อให้ลดขนาดลง แทนที่คีย์ด้วยคีย์ที่เล็กกว่า จากนั้นรวมผลลัพธ์กลับเข้าไปในฮีป
- ลบนาที − ฟังก์ชันนี้มีหน้าที่ในการลบรูทและทำการรวมทรีย่อยซ้ำๆ กันจนกว่าต้นไม้ต้นหนึ่งจะเหลืออยู่ ใช้กลยุทธ์การรวมต่างๆ
- แต่ละโหนดมีตัวชี้ไปทางลูกด้านซ้าย และปล่อยให้ลูกชี้ไปทางพี่น้องคนถัดไปของเด็ก
- ตัวอย่างการจับคู่ฮีปด้านล่าง -
การวิเคราะห์ความซับซ้อนของเวลาของการจับคู่ฮีปนั้นได้รับแรงบันดาลใจหลักจากความซับซ้อนของการแบ่งเวลา เวลาตัดจำหน่ายต่อการลบนาทีถือเป็น O(log n) และการดำเนินการ find-min, meld และ insert run ใน O(1) เวลาตัดจำหน่าย
