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

ฟิโบนักซี่ ฮีพ

(Fibonacci Heap)

            ฟิโบนักชี่ฮีพ จัดได้ว่าเป็นส่วนขยายของเลซี่ไบโนเมียลฮีพ กล่าวคือเป็นรายการของต้นไม้ที่เรียงลำดับแบบฮีพ โดยต้นไม้แต่ละต้นมีรากเป็นโหนดที่มีค่าน้อยที่สุด และต้นไม้ในฟิโบนักชี่ฮีพจะไม่มีข้อจำกัดดั่งเช่นต้นไม้ไบโนเมียล นอกจากนี้ในฟิโบนักชี่ฮีพยังสามารถมีต้นไม้ที่มีความสูงเท่ากันได้หลายต้น สำหรับในการวิเคราะหถัวเฉลี่ย จะขอใช้วิธีศักย์ โดยสมมติให้ฟิโบนักชี่ฮีพ H มีจำนวนต้นไม้ t(H) ต้น และมีจำนวนโหนดที่ถูกมาร์ค m(H) โหนด ดังนั้นฟังก์ชันศักย์  เป็น  = t(H) + 2m(H)

การปฏิบัติการของฟิโบนักชี่ฮีพ

  1. การหาโหนดที่มีค่าน้อยที่สุด   การหาโหนดที่มีค่าน้อยที่สุดใช้เวลา O(1) โดยการจำและปรับเปลี่ยนตำแหน่งของโหนด ที่มีค่าน้อยสุดไว้ตลอดเวลา เมื่อมีการเปลี่ยนแปลงเกิดขึ้นระหว่างการปฏิบัติการต่างๆ

  2. การเพิ่มข้อมูล ทำได้โดยการสร้างฮีพใหม่ที่มีข้อมูลเพียง 1 โหนด จากนั้นนำไปต่อกับรายการต้นไม้ของฮีพเดิม เวลาที่ใช้ในการเพิ่มจึงคงที่เพียง O(1) สามารถคิดต้นทุนที่ถัวเฉลี่ยได้ดังนี้
    = 1 + (t(H) + 1 + 2m(H))-(t(H) + 2m(H)) = 1 + 1 = 2
    หลังจากการเพิ่มโหนดเข้าไปในฮีพ ต้นไม้จะเพิ่มขึ้นในฮีพ 1 ต้น แต่จำนวนโหนดที่ถูกมาร์คจะไม่มีการเปลี่ยนแปลง สังเกตหลังจากการแทรกจะมีต้นไม้ที่มีความสูง 0 จำนวน 2 ต้นหรือมากกว่า
    อัลกอริทึมการแทรกเป็นดังนี้

FIB-HEAP-INSERT (H,X)
1. degree [X] <-- 0
2. p[X] <-- NIL
3. child [X] <-- NIL
4. left [X] <-- X
5. right [X] <-- X
6. mark [X] <-- FALSE
7. concatenate the root list containing X with root list H
8. if min [H] = NIL or key[X] < key[min[H]]
9. then min[H] <-- X
10. n[H] <-- n[H] + 1

  1. การรวมฮีพ เช่นเดียวกับเลซี่ไบโนเมียลฮีพ ทำได้โดยการสร้างฮีพใหม่ที่ประกอบไปด้วยต้นไม้ในฮีพแต่ละฮีพมาต่อกัน โดยในการรวมฮีพในฟิโบนักซี่ฮีพนั้นไม่จำเป็นต้องทำการเชื่อมต้นไม้ที่มีดีกรีเท่ากัน ใช้เวลาเพียง O(1) สามารถคิดต้นทุนถัวเฉลี่ยได้ดังนี้
    = 1 + (t(H) + 2m(H)) - (t(H1) + 2m(H1) + (t(H2) + 2m(H2))
    เนื่องจาก t(H1) = t(H2) และ m(H) = m(H1) + m(H2) ดังนั้น = 1 + 0 = 1 นั่นคือ หลังจากการรวมฮีพ 2 ฮีพ จำนวนต้นไม้ และจำนวนโหนดที่ถูกมาร์คจะไม่มีการเปลี่ยนแปลง สังเกต หลังจากการรวมฮีพแล้ว จะมีต้นไม้ที่มีความสูงเท่ากันอยู่หลายต้น
    อัลกอริทึมการรวมเป็นดังนี้

FIB-HEAP-UNION (H1, H2)
1. H <-- MAKE-FIB-HEAP ( )
2. Min[H] <-- min[H1]
3. Concatenate the root list of H2 with the root list of H
4. if (min[H1] = NIL) or (min[H2] <> NIL and min[H2] < min[H1]
5. then min[H] <-- min[H2]
6. n[H] <-- n[H1]+n[H2]
7. free the objects H1 and H2
8. return H

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

    ให้ r เป็น ระดับความสูงของต้นไม้ที่มีโหนดที่มีค่าน้อยที่สุด
    t เป็น จำนวนต้นไม้ในฮีพ

            ฟังก์ชันศักย์ก่อนการดำเนินงานการลบเป็น t+2m หลังจากทำการลบโหนดที่มีค่าน้อยที่สุดออก มีต้นไม้ย่อยที่แตกออกมา t+r ต้น ซึ่งในการรวมต้นไม้เหล่านี้ ต้นทุนจริงเป็น t+r+log n ฟังก์ชันศักย์จะเพิ่มขึ้นอย่างมาก ((log n)+2m)-(t+2m) = log n - t ต้นทุนถัวเฉลี่ยเป็น t+r+log n+log n-t = 2(log n)+r ที่ซึ่ง r < log n นั่นคือ ต้นทุนถัวเฉลี่ยเป็น O(log n)
อัลกอริทึมการลบเป็นดังนี้

FIB-HEAP-EXTRACT-MIN(H)
1. Z <-- MIN[H]
2. if Z <-- NIL
3. then for each child x of z
4. do add x to the root list of H
5. p[X] <-- NIL
6. remove z from the root list of H
7. if z = right[Z]
8. then min[H] <-- NIL
9. else min[H] <-- right[Z]
10. CONSOLIDATE(H)
11. n[H] <-- n[H] - 1
12. return z
CONSOLIDATE(H)
1. for I <-- 0 to D(n[H])
2. do A[I] <-- NIL
3. for each node wpe5.jpg (744 bytes) in the root list of H
4. do X <-- wpe5.jpg (744 bytes)
5.  d <-- degree[X]
6. while A[d] <> NIL
7. do Y<-- A[d]
8. if key[X] > key[Y]
9. then exchange X <---> Y
10. FIB-HEAP-LINK(H, Y, X)
11. A[d] <-- NIL
12. d <-- d + 1
13. A[d] <-- x
14. min[H] <-- NIL
15. for I <-- 0 to D(n[H])
16. do if A[I] <> NIL
17. then add A[I] to the root list of H
18. if min[H] = NIL or key[A[I]] < key[min[H]]
19. then min[H] <-- A[I]
FIB-HEAP-LINK(H,Y,X)
1.    remove Y from the root list of H
2.    make Y a child of X, incrementing degree[X]
3.    mark[Y] <-- FALSE

  1. การลดค่าของโหนด เป็นดังนี้
    1. ถ้าการลดค่าไม่เกิดการเปลี่ยนแปลงลำดับในฮีพให้ทำการลดค่าของโหนดใดๆ
    2. ถ้าการลดค่าก่อให้เกิดการเปลี่ยนแปลงลำดับในฮีพ กล่าวคือถ้าการลดค่าโหนด X ทำให้โหนด X มีค่าน้อยกว่าโหนดพ่อของโหนด X แล้วให้ทำการตัดโหนด X ออกจากโหนดพ่อของโหนด X
    3. โหนด X จะกลายราก(root) เป็นต้นไม้ใหม่
    4. ถ้า X เป็นลูกตัวแรกที่ถูกตัดจากโหนดพ่อของโหนด X แล้วทำการมาร์คโหนดพ่อของโหนด X
    5. ถ้า X เป็นไม่ใช่ลูกตัวแรกที่ตัดออกจากโหนดพ่อของโหนด X กล่าวคือ โหนดพ่อของโหนด X เป็นโหนดที่ถูกมาร์คก่อนแล้ว จะต้องทำการตัดโหนดพ่อของโหนด X ออกแล้วโหนดพ่อของโหนด X จะกลายเป็นราก เป็นต้นไม้ใหม่ แล้วทำการยกเลิกการมาร์คที่โหนดพ่อของโหนด X
    6. ย้อนกลับไปทำข้อ 5
    ในการวิเคราะห์ถัวเฉลี่ย สมมติให้ Cut เป็น จำนวนการตัดโหนดขณะทำการลดค่าโหนด ต้นทุนจริงเป็นสัดส่วนโดยตรงกับจำนวนการตัดบวก 1 สำหรับการตัดโหนดครั้งแรก นั่นคือ Ci = Cut + 1 โดยในการตัดโหนดครั้งแรกนั้นมีการสร้างต้นไม้ใหม่ เป็นการเพิ่มฟังก์ชันศักย์ขึ้น 1 หน่วย ในการตัดครั้งสุดท้ายมีการเพิ่มโหนดที่ถูกมาร์คอีก 1 เป็นการเพิ่มฟังก์ชันศักย์ขึ้น 2 หน่วย ในแต่ละครั้งของการตัด โหนดที่ถูกมาร์คอยู่ จะกลายเป็นโหนดที่ไม่ถูกมาร์คแล้ว เป็นการลดฟังก์ชันศักย์ตามจำนวนการตัดโหนด นั่นคือ - = 3-Cut ต้นทุนถัวเฉลี่ย จึงเป็น = Cut + 1 + 3-Cut = 4 นั่นคือ เวลาที่ใช้ในการลดค่าของโหนด เป็น O(1)
    อัลกอริทึมการลดค่าของโหนดเป็นดังนี้

    FIB-HEAP-DECREASE-KEY (H,X,K)
    1. if K > key[X]
    2. then error "new key is greater than current key"
    3. key[X] <-- K
    4. Y <-- p[X]
    5. if Y <> NIL and key[X] < key[Y]
    6. then CUT (H, X, Y)
    7. CASCADING-CUT (H, Y)
    8. if key[X] < key[min[H]]
    9. then min[H] <-- X
    CUT (H, X, Y)
    1. remove X from the child list of Y, decrementing degree[Y]
    2. add X to the root list of H
    3. p[X] <-- NIL
    4. mark[X] <-- FALSE
    CASADING-CUT (H, Y)
    1. Z <-- p[Y]
    2. if Z <> NIL
    3. then if mark[Y] = FALSE
    4. then mark[Y] <-- TRUE
    5. else CUT (H, Y, Z)
    6. CASADING-CUT (H, Z)

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

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

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