ทวินามฮีปในโครงสร้างข้อมูล

binomial Heap คือกลุ่มของต้นไม้ทวินาม ต้นไม้ทวินาม Bk เป็นต้นไม้ที่มีลำดับซึ่งกำหนดแบบเรียกซ้ำ ทวินามทรี B0 ประกอบด้วยโหนดเดียว

ต้นไม้ทวินาม Bk ประกอบด้วยต้นไม้ทวินาม Bk-1 สองต้น ที่เชื่อมโยงกัน. รูทของอันหนึ่งเป็นรูทย่อยด้านซ้ายสุดของรูทของอีกอันหนึ่ง

ฮีปทวินามบางส่วนมีลักษณะดังนี้ -

คุณสมบัติบางประการของต้นไม้ทวินามคือ −

• ต้นไม้ทวินามที่มี B_k มี 2_k โหนด

• ความสูงของต้นไม้คือ k

• มี $$\left(\begin{array}{c}k\\ j\end{array}\right)$$ nodes ที่ระดับความลึก i สำหรับ i ทั้งหมดในช่วง 0 ถึง k

ทวินามฮีป

ทวินามฮีป H คือชุดของต้นไม้ทวินาม มีคุณสมบัติบางอย่าง

• ต้นไม้ทวินามแต่ละต้นใน H นั้นเรียงลำดับกันแบบกอง ดังนั้นคีย์ของโหนดจึงมากกว่าหรือเท่ากับคีย์ของพาเรนต์

• มีต้นไม้ทวินามอย่างน้อยหนึ่งต้นใน H ซึ่งรากมีระดับที่กำหนด

ตัวอย่างของ Binomial Heap

Heap H ทวินามนี้ประกอบด้วยต้นไม้ทวินาม B0, B2 และ B3 ซึ่งมี 1, 4 และ 8 โหนดตามลำดับ และทั้งหมด n =13 โหนด รากของต้นไม้ทวินามเชื่อมโยงกันโดยลำดับของระดับที่เพิ่มขึ้น