Binomial Heap ถูกกำหนดให้เป็นส่วนขยายของ Binary Heap ที่ให้การรวมหรือการรวมตัวที่รวดเร็วขึ้นพร้อมกับการดำเนินการอื่น ๆ ที่จัดทำโดย Binary Heap
Binomial Heap ถือเป็นกลุ่มของต้นไม้ทวินาม
ต้นไม้ทวินามคืออะไร
ต้นไม้ทวินามของคำสั่ง k สามารถสร้างได้โดยใช้ต้นไม้ทวินามที่มีลำดับ k-1 สองต้น และถือว่าต้นหนึ่งเป็นลูกที่อยู่ทางซ้ายสุดหรือต้นอื่น
ทวินามทรีของคำสั่ง k มีคุณสมบัติด้านล่าง
-
จำนวนโหนดของ Binomial Tree มี 2 k .
-
ความลึกของต้นไม้ทวินามคือ k.
-
มีโหนด kCi อยู่ที่ระดับความลึก i โดยที่ i =0, 1, . . , k.
-
รากที่มีดีกรี k และลูกของรูตจะถือว่าเป็นต้นไม้ทวินามด้วยลำดับ k-1, k-2,..0 จากซ้ายไปขวา
ทวินามฮีป −
Binomial Heap ถูกกำหนดให้เป็นชุดของ Binomial Tree โดยที่ Binomial Tree แต่ละอันตามหลังคุณสมบัติของ MinHeap และไม่ว่าจะมีดีกรีใดก็ตาม ก็สามารถมีต้นไม้ทวินามที่มีดีกรีได้ไม่เกินหนึ่งต้น
ตัวอย่างทวินามฮีป −
Binomial Heap มี 12 โหนด ถือว่าเป็นคอลเลกชั่น 2
จากซ้ายไปขวา ต้นไม้ทวินามของคำสั่ง 2 และ 3
ทวินามฮีปและการแทนค่าไบนารีของตัวเลข
ทวินามฮีปที่มีโหนด m มีจำนวนต้นไม้ทวินามเท่ากับจำนวนเซ็ตบิตในการแทนค่าไบนารีของ ม. ตัวอย่างเช่น สมมติว่า m เป็น 13 มี 3 ชุดบิตในการแทนค่าไบนารีของ m (00001101) ซึ่งระบุ 3 Binomial Trees นอกจากนี้เรายังสามารถเชื่อมโยงระดับของต้นไม้ทวินามเหล่านี้กับตำแหน่งของเซตบิตได้ ด้วยความช่วยเหลือของความสัมพันธ์นี้ เราสามารถตัดสินใจหรือสรุปว่ามี O(logm) Binomial Trees ใน BinomialHeap ที่มีโหนด 'm'
การทำงานของ Binomial Heap -
union() เป็นการดำเนินการหลักใน Binomial Heap ส่วนการดำเนินการอื่นๆ ทั้งหมดจะใช้การดำเนินการนี้เป็นหลัก การดำเนินการ union() มีหน้าที่ในการรวม Binomial Heaps สองกองเข้าด้วยกัน
-
insert(h, K)− แทรกคีย์ 'K' ไปยัง Binomial Heap 'h' ในตอนแรก การดำเนินการนี้สามารถสร้าง Binomial Heap ด้วยคีย์เดียว 'K' จากนั้นเรียก union บน h และ Binomial heap ใหม่
-
getMin(h)− วิธีง่ายๆ ในการ getMin() คือไปที่รายการรูทของทวินามทรีและส่งคืนคีย์ที่เล็กที่สุด
แอปพลิเคชันนี้ต้องใช้เวลา O (logm) สามารถปรับปรุงเป็น O(1) ได้โดยการรักษาตัวชี้ไปยังรูทคีย์ที่เล็กที่สุด
-
extractMin(h)− การดำเนินการนี้ยังใช้ union() ในตอนแรก เราเรียก getMin() เพื่อคำนวณ Binomial Tree คีย์ที่เล็กที่สุด ต่อไปเราจะลบโหนดและสร้าง Binomial Heap ใหม่โดยการรวมทรีย่อยทั้งหมดของโหนดที่เล็กที่สุดที่ถูกลบออก ในที่สุด เราก็ callunion() บน h เช่นเดียวกับ Binomial Heap ที่สร้างขึ้นใหม่ การดำเนินการนี้ต้องใช้เวลา O(logm)
-
delete(h)− เหมือนกับ Binary Heap ในตอนแรก การลบจะลดคีย์เป็น minusinfinite โทรถัดไป extractMin()
-
ลดKey(h)− reduceKey() ก็เหมือนกับ Binary Heap ในตอนแรก เราเปรียบเทียบคีย์ที่ลดลงกับคีย์หลัก และถ้าคีย์ของพาเรนต์มีมากกว่า เราจะแลกเปลี่ยนคีย์และดำเนินการกับคีย์หลักซ้ำ ในที่สุด เราหยุดเมื่อเราไปถึงโหนดที่มีผู้ปกครองที่มีคีย์ที่เล็กกว่าหรือเรามาถึงโหนดรูท ความซับซ้อนของเวลาของ reduceKey() คือ O(logm)
