ผู้ใช้:KLadarat/ไบโนเมียล ฮีฟ

ไบโนเมียล ฮีฟ

ไบโนเมียล ฮีฟ มีคุณสมบัติของการเป็น ไบโนเมียลทรี แต่ละต้นไม้จะมีองค์ประกอบที่เรียกว่าดีกรี

• ไบโนเมียลทรี ดีกรี 0 หรือ B₀ จะมีโหนดจำนวน 1 โหนด
• ไบโนเมียลทรี ดีกรี 1 หรือ B₁ จะมีโหนดจำนวน 2 โหนด
• ไบโนเมียลทรี ดีกรี 2 หรือ B₂ จะมีโหนดจำนวน 4 โหนด

…

• ไบโนเมียลทรี ดีกรี k หรือ B_k จะมีโหนดจำนวน 2^k โหนด

ลักษณะของต้นไม้ไบโนเมียลหรือไบโนเมียลทรี

โดยไบโนเมียลทรี B_k = B_k-1 + B_k-1 นั่นคือ ไบโนเมียลทรี ดีกรี k จะประกอบด้วย 2 ไบโนเมียลทรี ดีกรี k-1

คุณสมบัติการเป็นต้นไม้ไบโนเมียลของไบโนเมียล ฮีฟ

การปฏิบัติการ

การเพิ่ม

มีขั้นตอนดังนี้

การเพิ่มโหนด โดยแสดงการเพิ่มที่ละโหนดเข้าไปในฮีฟ

1. สร้างโหนดใหม่จากค่าที่เพิ่มเข้ามา
2. หากโหนดที่เพิ่มเข้ามามีดีกรีเท่ากับโหนดที่มีอยู่ให้รวมเข้ากับโหนดที่มีอยู่โดยหากโหนดที่เพิ่มเข้ามามีค่าน้อยกว่าให้โหนดนั้นเป็นราก แต่หากโหนดที่เพิ่มเข้ามามีค่ามากกว่าให้โหนดนั้นเป็นโหนดลูก โดยมีโหนดที่มีค่าน้อยกว่านั้นเป็นราก ซึ่งในขั้นตอนนี้ ถูกเรียกว่าการรวมซึ่งจะกล่าวต่อไป

การหาค่าน้อยที่สุด

คือการหาค่าน้อยที่สุดที่อยู่ในไบโนเมียล ฮีฟ

การหาค่าน้อยที่สุดหลังจากมีการเพิ่มค่าเข้ามาทีละค่า

การลบค่าน้อยที่สุด

คือลบค่าที่เป็นค่าน้อยที่สุดในไบโนเมียล ฮีฟ ออก โดยมีขั้นตอนดังนี้

แสดงการลบค่าที่น้อยที่สุดแล้ว เกิดการรวมเกิดขึ้น

1. ลบค่าที่น้อยที่สุดในไบโนเมียล ฮีฟ
2. หากโหนดที่ถูกลบออกไปมีโหนดลูก ให้โหนดลูกนั้นขึ้นมาเป็นราก
3. หากมีต้นไม่ที่มีขนาดดีกรีเท่ากันเกิดขึ้นจากการลบ ให้ทำการรวม ไม่ให้มีต้นไม้ที่มีขนาดดีกรีเท่ากัน

การรวม

มีขั้นตอนดังนี้

แสดงการลบค่าที่น้อยที่สุดแล้ว เกิดการรวมเกิดขึ้น

1. รวมเอาต้นไม้ที่มีขนาดดีกรีเท่ากันรวมเข้าด้วยกันเป็นต้นไม้เดียว
2. หากรากของต้นไม้ใดมีค่าน้อยกว่าให้โหนดนั้นเป็นรากเมื่อมีการรวมเกิดขึ้น
3. โดยการรวมนี้จะทำจนกว่าไม่มีต้นไม้ที่มีขนาดดีกรีเท่ากัน

การลดคีย์

คือการลำดับข้อมูลให้ถูกต้องตามคุณสมบัติของไบโนเมียล ฮีฟ หากค่าน้อยที่สุดไม่ได้เป็นราก ให้สลับขึ้นมาจนกว่าค่าน้อยสุดนั้นจะเป็นรากของต้นไม้

เป็นนำค่าน้อยที่สุดขึ้นมาเป็นรูท