[การวิเคราะห์อัลกอริทึม] [ตารางไดนามิก] [ไบโนเมียลฮีพ] [เลซี่ไบโนเมียลฮีพ] [ฟิโบนักซี่ฮีพ] [สคริวฮีพ][รายการอ้างอิง]

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

(Binomial Heap)

นิยาม   ต้นไม้ไบโนเมียล Bk เป็นต้นไม้ที่มีการเรียงลำดับ โดยที่

ต้นไม้ไบโนเมียล B0 จะประกอบด้วยโหนดโหนดเดียว

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

        ต้นไม้ไบโนเมียล B0   ถึง B3  แสดงได้ดังรูป

ex.JPG (10858 bytes)

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

    สำหรับการวิเคราะห์ถัวเฉลี่ยจะขอใช้วิธีศักย์ โดยที่ฟังก์ชันศักย์คิดจากจำนวนของต้นไม้

การปฏิบัติการบนไบโนเมียล ฮีพ

  1. การหาโหนดที่มีค่าน้อยที่สุด การหาโหนดที่มีค่าน้อยที่สุดใช้เวลา O(1) โดยการจำและปรับเปลี่ยนตำแหน่งของโหนด ที่มีค่าน้อยสุดไว้ตลอดเวลา เมื่อมีการเปลี่ยนแปลงเกิดขึ้นระหว่างการปฏิบัติการต่างๆ
    อัลกอริทึมการหาโหนดที่มีค่าน้อยที่สุด มีดังต่อไปนี้
BINOMAIL-HEAP-MINIMUM ( H )
1. y <-- NIL
2. x <-- head[H]
3. min <--
4. while x <> NIL
5. do if key[x] < min
6. then min <-- key[x]
7. y <-- x
8. x <-- sibling[x]
9. return y
  1. การรวมฮีพ   การรวมไบโนเมียลฮีพ 2 ฮีพ มีขั้นตอน
    2.1    เชื่อมรากของต้นไม้ในฮีพทั้ง 2 เข้าด้วยกัน
    2.2    ถ้าในฮีพมีต้นไม้ที่มีความสูงเท่ากัน เชื่อมต้นไม้นั้นเข้าด้วยกัน โดยให้รากที่มีค่าน้อยกว่า เป็นรากของต้นไม้ที่เชื่อมรวมกันแล้ว ดังนั้นต้นไม้ B(k-1) จำนวน 2 ต้น จะรวมเป็นต้นไม้ Bk ที่มีรากเป็นค่าที่น้อยกว่า
    2.3   ทำ 2.2 ไปเรื่อยๆจนกว่าจะไม่มีต้นไม้ที่มีความสูงเท่ากัน
    เวลาการรวมจะขึ้นอยู่กับจำนวนต้นไม้ในฮีพ ซึ่งจะมีอย่างมากสุด log n ต้น ดังนั้น การรวมฮีพ 2 ฮีพใช้เวลา O(log n)
    อัลกอริทึมการรวมมีดังต่อไปนี้
BINOMAIL-HEAP-UNION ( H1 , H2 )
1. H <-- MAKE-BINOMAIL-HEAP( )
2. head[H] <-- BINOMAIL-HEAP-MERGE ( H1 , H2 )
3. free the objects H1 and H2 but not the lists they point to
4. if head[H] = NIL
5. then return H
6. prev-x <-- NIL
7. x <-- head[H]
8. next-x <-- sibling[x]
9. while next-x <-- NIL
10. do if (degree[x] <> degree[next-x]) or (sibling[next-x]) <> NIL and degree[sibling[next-x]] = degree[x])
11. then prev-x <-- x
12. x <-- next-x
13. else if key[x] < key[next-x]
14. then sibling[x] <-- sibling[next-x]
15. BINOMAIL-LINK(next-x,x)
16. else if prev-x = NIL
17. then head[H] <-- next-x
18. else sibling[prev-x] <-- next-x
19. BINOMAIL-LINK(x,next-x)
20. x <-- next-x
21. next-x <-- sibling[x]
22. return H
BINOMIAL-LINK(y,z)
1. p[y] <-- z
2. sibling[y] <--  child[z]
3. child[z] <--  y
4. degree[z]  <--  degree[z]+1
  1. การเพิ่ม     การเพิ่มข้อมูลในฮีพ มีขั้นตอนดังนี้
    3.1     สร้างฮีพใหม่ที่ประกอบด้วยโหนดใหม่ที่มาเพิ่ม ที่ซึ่งใช้เวลา O(1)
    3.2    นำฮีพใหม่ที่สร้างขึ้น รวมเข้ากับฮีพเดิมที่มีอยู่ ใช้เวลาในการO( log n )
    ดังนั้นหากกำหนดให้ฟังก์ชันศักย์เป็นจำนวนต้นไม้ในฮีพ ต้นทุนถัวเฉลี่ยจะเท่ากับต้นทุนจริงบวกกับจำนวนต้นไม้ที่เปลี่ยนแปลง ถ้าต้นทุนจริงในการเพิ่มเป็น v แสดงว่าต้นไม้ B0, B1, … , B(v-2) เดิมในฮีพ รวมกับต้นไม้ B0 ในฮีพใหม่ จะกลายเป็นต้นไม้ B(v-1) 1 ต้น จำนวนต้นไม้ที่เปลี่ยนแปลงจะเท่ากับ 1-(v-1) ดังนั้น ต้นทุนถัวเฉลี่ยในการเพิ่มเท่ากับ v+(1-(v-1)) = 2 = O(1)
    อัลกอริทึมการแทรก มีดังต่อไปน
ี้BINOMIAL-HEAP-INSERT (H,x)
1. H' <-- MAKE-BINOMIAL-HEAP( )
2. p[x] <-- NIL
3. child[x] <-- NIL
4. sibling[x] <-- NIL
5. degree[x] <-- 0
6. head[H'] <-- x
7. H <-- BINOMIAL-HEAP-UNION(H,H')
  1. การลบโหนดที่มีค่าน้อยที่สุด     การลบโหนดที่มีค่าน้อยที่สุด มีขั้นตอนดังนี้
    4.1     หาโหนดที่เป็นรากของต้นไม้ ที่มีค่าน้อยสุด แล้วลบออก
    4.2    สร้างฮีพใหม่ ซึ่งประกอบไปด้วยรายการของต้นไม้ย่อยของโหนดที่ถูกลบออก
    4.3     รวมฮีพใหม่นี้กับฮีพเดิมที่ได้นำต้นไม้ที่มีโหนดที่รากมีค่าน้อยที่สุดออกแล้ว
    การหาโหนดที่เป็นรากของต้นไม้ ที่มีค่าน้อยสุด ใช้เวลา O(1) ส่วนการลบรากของต้นไม้ซึ่งมีค่าน้อยสุด ใช้เวลา O(1) การสร้างฮีพใหม่ใช้เวลา O(log n) และการรวมฮีพเข้าด้วยกัน ใช้เวลา O(lg n) ดังนั้นเวลาที่ใช้ในการลบโหนดที่มีค่าน้อยที่สุดเป็น O(lg n) ดังอัลกอริทึมต่อไปนี้
    อัลกอริทึมการลบมีดังต่อไปนี้
BINOMIAL-HEAP-EXTRACT-MIN(H)
1. find the root x with the minimum key in the root list of H, and remove x from the root list of H
2. H' <-- MAKE-BINOMIAL-HEAP( )
3. Reverse the order of the linked list of x's children, and set head[H'] to point to the head of the resulting list
4. H <-- BINOMIAL-HEAP-UNION(H,H')
5. return x

การจินตทัศน์

การจินตทัศน์การวิเคราะหถัวเฉลี่ย ไบโนเมียลฮีพ ในการดำเนินงานการแทรก การลบโหนดที่มีค่าน้อยที่สุด และการลดค่าคีย์
การจินตทัศน์การวิเคราะหถัวเฉลี่ย ไบโนเมียลฮีพ ในการดำเนินงานการรวมฮีพ

[การวิเคราะห์อัลกอริทึม] [ตารางไดนามิก] [ไบโนเมียลฮีพ] [เลซี่ไบโนเมียลฮีพ] [ฟิโบนักซี่ฮีพ] [สคริวฮีพ][รายการอ้างอิง]