ผู้ใช้:KLadarat/ไบโนเมียล ฮีฟ
ไบโนเมียล ฮีฟ
แก้ไบโนเมียล ฮีฟ มีคุณสมบัติของการเป็น ไบโนเมียลทรี แต่ละต้นไม้จะมีองค์ประกอบที่เรียกว่าดีกรี
- ไบโนเมียลทรี ดีกรี 0 หรือ B0 จะมีโหนดจำนวน 1 โหนด
- ไบโนเมียลทรี ดีกรี 1 หรือ B1 จะมีโหนดจำนวน 2 โหนด
- ไบโนเมียลทรี ดีกรี 2 หรือ B2 จะมีโหนดจำนวน 4 โหนด
…
- ไบโนเมียลทรี ดีกรี k หรือ Bk จะมีโหนดจำนวน 2k โหนด
โดยไบโนเมียลทรี Bk = Bk-1 + Bk-1 นั่นคือ ไบโนเมียลทรี ดีกรี k จะประกอบด้วย 2 ไบโนเมียลทรี ดีกรี k-1
การปฏิบัติการ
แก้การเพิ่ม
แก้มีขั้นตอนดังนี้
- สร้างโหนดใหม่จากค่าที่เพิ่มเข้ามา
- หากโหนดที่เพิ่มเข้ามามีดีกรีเท่ากับโหนดที่มีอยู่ให้รวมเข้ากับโหนดที่มีอยู่โดยหากโหนดที่เพิ่มเข้ามามีค่าน้อยกว่าให้โหนดนั้นเป็นราก แต่หากโหนดที่เพิ่มเข้ามามีค่ามากกว่าให้โหนดนั้นเป็นโหนดลูก โดยมีโหนดที่มีค่าน้อยกว่านั้นเป็นราก ซึ่งในขั้นตอนนี้ ถูกเรียกว่าการรวมซึ่งจะกล่าวต่อไป
การหาค่าน้อยที่สุด
แก้คือการหาค่าน้อยที่สุดที่อยู่ในไบโนเมียล ฮีฟ
การลบค่าน้อยที่สุด
แก้คือลบค่าที่เป็นค่าน้อยที่สุดในไบโนเมียล ฮีฟ ออก โดยมีขั้นตอนดังนี้
- ลบค่าที่น้อยที่สุดในไบโนเมียล ฮีฟ
- หากโหนดที่ถูกลบออกไปมีโหนดลูก ให้โหนดลูกนั้นขึ้นมาเป็นราก
- หากมีต้นไม่ที่มีขนาดดีกรีเท่ากันเกิดขึ้นจากการลบ ให้ทำการรวม ไม่ให้มีต้นไม้ที่มีขนาดดีกรีเท่ากัน
การรวม
แก้มีขั้นตอนดังนี้
- รวมเอาต้นไม้ที่มีขนาดดีกรีเท่ากันรวมเข้าด้วยกันเป็นต้นไม้เดียว
- หากรากของต้นไม้ใดมีค่าน้อยกว่าให้โหนดนั้นเป็นรากเมื่อมีการรวมเกิดขึ้น
- โดยการรวมนี้จะทำจนกว่าไม่มีต้นไม้ที่มีขนาดดีกรีเท่ากัน
การลดคีย์
แก้คือการลำดับข้อมูลให้ถูกต้องตามคุณสมบัติของไบโนเมียล ฮีฟ หากค่าน้อยที่สุดไม่ได้เป็นราก ให้สลับขึ้นมาจนกว่าค่าน้อยสุดนั้นจะเป็นรากของต้นไม้