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

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

(Lazy Binomial Heap)

            เลซี่ไบโนเมียลฮีพ มีลักษณะการจัดเก็บ และการจัดการคล้ายกับไบโนเมียลฮีพ คือเป็นรายการของต้นไม้ไบโนเมียล แต่ต่างกันตรงที่เลซี่ไบโนเมียลฮีพ สามารถมีต้นไม้ที่มีความสูงเท่ากันได้มากกว่า 1 ต้น

นิยาม เลซี่ ไบโนเมียล ฮีพ H มีคุณสมบัติ ดังนี้

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

เลซี่ไบโนเมียลฮีพ H สามารถมีต้นไม้ไบโนเมียลที่มีความสูงเท่ากันได้มากกว่า 1 ต้น 

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

การปฏิบัติการของเลซี่ ไบโนเมียล ฮีพ

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

  2. การรวมฮีพ การรวมฮีพทำได้โดยการสร้างฮีพใหม่ ที่ประกอบไปด้วยต้นไม้ในฮีพแต่ละฮีพมาต่อกัน โดยในการรวมฮีพในเลซี่ไบโนเมียลฮีพนั้นไม่จำเป็นต้องทำการเชื่อมต้นไม้ที่มีดีกรีเท่ากัน ดังนั้นจึงใช้เวลาเพียง O(1)
    อัลกอริทึมการรวมมีดังต่อไปนี้

    LAZY-BINOMIAL-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

  3. การเพิ่มข้อมูล   การเพิ่มข้อมูล ทำได้โดยการสร้างฮีพใหม่ที่มีข้อมูลเพียง 1 โหนด จากนั้นนำไปต่อกับรายการต้นไม้ของฮีพเดิม จึงใช้เวลาในการเพิ่มเพียง O(1)    
    อัลกอริทึมการเพิ่ม มีดังต่อไปนี้

    LAZY-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. return H'

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

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

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

LAZY-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

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

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

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