รูปแบบของการจับคู่ฮีป

ฮีปการจับคู่สามารถเป็นได้ทั้งฮีปว่าง หรือทรีการจับคู่ที่มีองค์ประกอบรูทและรายการทรีที่จับคู่อาจว่างเปล่า

คุณสมบัติการเรียงลำดับฮีปต้องการให้พาเรนต์ของโหนดใด ๆ ไม่มากกว่าตัวโหนดเอง

คำอธิบายต่อไปนี้พิจารณาถึงฮีปที่ใช้งานได้จริงซึ่งไม่สนับสนุนการทำงานของคีย์ลด

ชนิด PairingTree[Element] =Heap(องค์ประกอบ:Element, subheaps:List[PairingTree[Element]])

พิมพ์ PairingHeap[องค์ประกอบ] =ว่าง | PairingTree[องค์ประกอบ]

ฮีปการจับคู่มีอยู่สองแบบ - ฮีปการจับคู่ขั้นต่ำ และ ฮีปการจับคู่สูงสุด ฮีปการจับคู่ขั้นต่ำจะถูกนำไปใช้เมื่อเราต้องการแสดงคิวที่มีลำดับความสำคัญขั้นต่ำ และฮีปการจับคู่สูงสุดจะถูกนำไปใช้สำหรับคิวที่มีลำดับความสำคัญสูงสุด ตามการสนทนาของเราเกี่ยวกับฮีปและทรีฝ่ายซ้ายในข้อความ เราได้กล่าวถึงฮีปการจับคู่สูงสุดอย่างชัดเจนที่นี่ ฮีปการจับคู่ขั้นต่ำสามารถเปรียบเทียบได้

ฮีปการจับคู่สูงสุดถูกกำหนดให้เป็นต้นไม้สูงสุด

แสดงฮีปการจับคู่สูงสุดสี่รายการด้านล่าง สังเกตว่าการจับคู่ฮีปไม่จำเป็นต้องเป็นไบนารีทรี