การเก็บข้อมูลแบบ Binomial Queue
Binomial Queue
เป็นการเก็บข้อมูลไว้หลายๆ Heap โดยเรียงจาก Heap น้อยไปหา Heap มาก โดยแต่ละ Heap จะต้องเป็นไปตามกฏคือ
o
ถ้าต้นไม้มีความสูง k จะต้องมีโหนดในต้นไม้เพียงแค่ 2k เท่านั้น
เช่น Heap สูง 1 มี 1 โหนด, Heap สูง 2 มี 4 โหนด เป็นต้น
o
ที่ระดับความลึก (depth) d จะมีจำนวนโหนดอยู่ C(k, d) เท่านั้น เช่น
ที่ระดับความลึก 3 ของ Heap ที่สูง 4
จะมีจำนวนโหนดเป็น C(4, 3) = 4! / 3!1! = 4 โหนด
ตัวอย่างของ Heap ใน Binomial
Queue
Merge Binomial Queue
วิธีการ Merge รวมเอา Binomial
Queue 2 ตัวเข้าด้วยกัน โดยสมมุติว่ามี H1 และ
H2 เป็น Binomial Queue ดังนี้
สมมุติว่าเราสร้าง H3 เป็น Binomial
Queue ตัวใหม่ ที่เตรียมไว้เก็บผลรวมของ H1 กับ
H2 ดังนี้
ตามกฏของ Heap ก็คือ
เราจะสแกนจาก B0 ก่อน จะเห็นว่า H1 ไม่มี
B0 หลักการรวมจะต้องรวมที่ k เดียวกัน
คือ B0 ก็ต้องรวมกับ B0 และ B1 ก็ต้องรวมกับ B1 เพราะจะต้องได้จำนวนโหนดเป็น 2k
เท่านั้น ดังนั้นที่ B0 นี้เราต้องข้ามไปก่อน
มาดูที่ B1 จะเห็นว่าทั้ง H1
กับ H2 มี B1 ด้วยกันทั้งคู่
B1 มีจำนวนโหนดเป็น 2 เสมอ
ดังนั้นเมื่อรวมเข้าด้วยกันจะได้จำนวนโหนดเป็น 2 + 2 = 4 ซึ่งต้องย้ายไปอยู่ที่
k = 2
ณ ที่ B1 การรวมจะดูว่า Root
ของ H1 หรือ H2 ใครที่มีค่ามากกว่าจะกลายไปเป็นลูกของอีกตัวหนึ่ง
ดังนี้
นำ Root 14 มาที่ B2 ของ H3 เพราะมีค่าน้อยกว่า จะต้องมาเป็นตัวแม่
หลังจากนั้นนำ Root 16 มาต่อเป็นลูกของ 14 ดังนี้
เมื่อจับ Root 16 ออกมาเป็นลูกของ
14 จะได้ Heap ระดับ k=2 อยู่ใน B2 ของ H3 ดังภาพข้างต้น
ต่อจากนั้นเราจะต้องรวมที่ระดับ B2 ของทั้ง H1, H2 และ H3 เข้าด้วยกัน
โดยเลือกมาเพียงคู่เดียว ซึ่งจะทำให้จำนวนโหนดเพิ่มจาก 4 กลายเป็น
8 และต้องย้ายไปอยู่ที่ระดับ k = 3 แทน
การเลือกจะเลือกจะยึดตัวที่อยู่ใน H3 เป็นหลัก
จากนั้นจะเลือกที่มากกว่าค่า Root 14 มาทำเป็นลูกของ Root
14 ในที่นี้ Root 23 ที่ H2 จึงเป็นตัวที่ถูกเลือกมาทำเป็นลูกของ Root 14 ดังนี้
เมื่อเสร็จขั้นนี้จะดูว่าเหลือ Heap อยู่ที่ k ระดับไหนอีก ที่ไม่สามารถจับคู่ได้
ในที่นี้จะเหลือ Heap อยู่ใน B0 และ B2
ของ H2 ซึ่งเราจะก็อปปีมาที่ H3 ซึ่งจะได้ผลลัพธ์ดังนี้
เมื่อรวมเสร็จจะได้ H3 เป็นผลรวมระหว่าง
H1 กับ H2 ตามภาพข้างต้น
Insertion
การใส่ค่าใหม่เข้ามาใน Binomial Queue จะใช้หลักการว่าจำนวนโหนดไปตกอยู่ที่ k ที่เท่าไร
การเพิ่มจะเพิ่มเข้าไปที่ k เล็กกว่าก่อนเสมอ
ถ้าจำนวนโหนดเกินกว่าจำนวนที่ระดับนั้นจะรับได้ จะปัดไปขึ้นที่ k ที่ใหญ่กว่า
ตัวอย่างเช่น ถ้า Insert 1 เข้าไปใน
Binomial Queue ว่าง จะต้องไปวางไว้ที่ B0 ก่อน
เมื่อ Insert 2 ตามเข้าไป 2
จะต่อเข้ากับ 1 และทำให้จำนวนโหนดเปลี่ยนจาก 1
กลายเป็น 2 ทำให้ไม่สามารถอยู่ที่ระดับ B0
ได้ จึงต้องปัดไปอยู่ที่ B1 แทน ดังนี้
เมื่อ Insert 3 ตามเข้าไป
เราจะวาง 3 ไว้ที่ B0 ดังนี้
เมื่อ Insert 4 ตามเข้าไป
เราจะวาง 4 ต่อจาก 3 ไว้ที่ B0 แต่ B0 ไม่สามารถรับจำนวนโหนด 2 โหนดได้ จึงต้องย้ายมา Merge รวมเข้าที่ระดับ B1
ทำให้ระดับ B1 ไม่สามารถรวมที่จำนวนโหนด 4
โหนดได้ สุดท้ายต้องย้ายไปวางที่ระดับ B2 แทน
เมื่อ Insert 5 เข้าไป
เราจะวาง 5 ไว้ที่ B0 ดังนี้
เมื่อ Insert 6 เข้าไป
เราต่อ 6 เข้ากับ 5 จะทำให้
ต้องย้ายจาก B0 มาอยู่ที่ระดับ B1 แทนดังนี้
เมื่อ Insert 7 เข้าไป จะวาง
7 ไว้ที่ B0 ดังนี้
เมื่อ Insert 8 เข้าไปจะนำ 8
ไปรวมกับ 7 ที่ B0 จากนั้นย้าย
มา Merge รวมเข้ากับ B1 ย้ายมา Merge
รวมเข้ากับ B2 สุดท้ายจะมีจำนวนโหนดทั้งหมด 8
โหนด ทำให้อยู่ที่ระดับ B2 ไม่ได้
ต้องย้ายไปอยู่ที่ระดับ B3 แทนดังนี้
Deletion
การลบโหนดออกจาก Binomial Queue ตามวิธีการ deleteMin เช่น จากภาพข้างบนถ้าเรา deleteMin
จะได้ค่า 1 กลับออกไป แต่ลูกๆของ 1 จะแตกกระจายออกมา เราจะใช้วิธีการสร้าง Binomial Queue ตัวใหม่ ที่เก็บโหนดที่แตกออกมาจากการลบ Root ทิ้งไปแล้วนำ
Binomial Queue ตัวนี้กลับเข้าไปรวมอีกครั้ง
ตัวอย่างเช่น ถ้าเรามี Binomial Queue อยู่ดังนี้
ถ้าเราจะ deleteMin เราจะต้องลบโหนด
2 ทิ้งไป ทำให้ลูกๆของ Root 2 ที่ระดับ B4
แตกออก 4 ตัว เราจะสร้าง Binomial
Queue ตัวใหม่เอาไว้พักลูกๆของ Root 2 เรียกว่าเป็น
H’ ดังนี้
และนำ H1 กับ H’ รวมกลับเข้าด้วยกันใหม่จะได้ผลลัพธ์ดังนี้
ความคิดเห็น
แสดงความคิดเห็น