Leftist Heap

Leftist Heap

วิธีการนับ null path length (npl) ก็คือ โหนดไหนไม่มีลูก หรือ มีลูกแค่ 1 ตัว เราให้ npl = 0 ส่วนโหนดมีลูกครบ 2 ตัว เราให้ npl = 1 ตัวอย่างการหาค่า npl ของ Heap ต่อไปนี้
เมื่อนับค่า npl ได้แล้ว เราจะตัดสินใจว่า Heap ไหนเป็น Leftist Heap โดยใช้กฏว่า “ทุกๆโหนดใน Heap ลูกด้านซ้ายต้องมีค่า npl มากกว่าหรือเท่ากับ ลูกด้านขวาเสมอ” ถ้ามีโหนดใน Heap ฝืนกฏนี้ถือว่า Heap นั้นทั้งตัวไม่เป็น Leftist Heap
ตัวอย่างของ Heap ที่เป็น Leftist และที่ไม่เป็น ดังภาพต่อไปนี้
ในภาพข้างบนนี้เป็น Leftist Heap เนื่องจากทุกๆโหนดใน Heap มีค่า npl ของลูกด้านซ้ายมากกว่าหรือเท่ากับลูกด้านขวาทั้งหมด (คือไม่ 1-0 ก็ 0-0 ถือว่าใช้ได้ แต่ถ้าเจอ 0-1 ถือว่าผิดกฏ)
ภาพนี้ Heap ไม่เป็น Leftist เพราะมีโหนดที่ฝืนกฏ โดยมี npl ของลูกด้านซ้ายเป็น 0 และ npl ลูกด้านขวาเป็น 1 ดังนั้นทั้ง Heap นี้ไม่เป็น Leftist

Merge Leftist Heap

เนื่องจาก Leftist Heap ทำมาไว้เพื่อให้การจับ Heap 2 ตัวมารวมกัน ทำได้ง่าย โดยใช้หลักการดังนี้
สมมุติว่ามี Leftist Heap 2 ตัว คือ H1 และ H2
o    ให้ Root ของ H1 น้อย Root ของ H2
o    ค้นเข้าไปใน H1 ด้านขวา หาว่ามีโหนดไหนที่มากกว่า Root ของ H2
o    หยิบโหนดที่มากกว่านั้นทั้งยวง (ทั้ง subtree) มาต่อเป็นลูกขวาของ H2
o    เอา H2 ไปต่อเป็นลูกด้านขวาของ H1
o    สลับลูกของ H1 ซ้ายไปอยู่ขวา และ ขวามาอยู่ซ้าย
o    จะได้ต้น H1 ที่เป็น Leftist และ Merge เข้ากับ H2 แล้ว
ตัวอย่างเช่นถ้าเรามี H1 กับ H2 เป็น Leftist Heap ดังภาพต่อไปนี้
สแกนด้านขวาของ H1 พบว่า 8 มีค่ามากกว่า 6 ดังนั้นหยุดไว้ที่ 8 ดังนี้
สแกนด้านขวาของ H2 พบว่า 7 มีลูกทั้ง 2 ตัวที่มากกว่า 8 ดังนั้นหยุดไว้ที่ 7 ดังนี้
นำลูกด้านขวาของ 7 ไปต่อเป็นลูกด้านขวาของ 8 ดังนี้
นำลูกด้านซ้ายของ 7 สลับมาเป็นลูกด้านขวา
นำโหนด 8 ที่หยุดไว้ที่ H1 ยกมาทั้งยวง มาเป็นลูกด้านขวาของ 7 ดังนี้
นำโหนด 6 (คือต้น H2 ทั้งต้น) ไปเป็นลูกด้านขวาของต้น H1 ดังนี้
เมื่อตรวจสอบจะพบว่าตอนนี้ ต้นที่รวมเข้าด้วยกันไม่เป็น Leftist แล้วเนื่องจากขวาหนักกว่าซ้าย ดังนั้น เราจะสลับแขนขวา และ แขนซ้าย สับเปลี่ยนกัน จะทำให้กลายเป็น Leftist เหมือนเดิมดังนี้
เมื่อสับเปลี่ยน ซ้าย-ขวา เรียบร้อยแล้ว ตรวจสอบอีกครั้งว่ายังคงมีสภาพเป็น Leftist Heap หรือไม่
ซึ่งพบว่ายังเป็น Leftist อยู่ และเราจะได้ต้น Heap ที่รวมระหว่าง H1 กับ H2

ความคิดเห็น

แสดงความคิดเห็น

โพสต์ยอดนิยมจากบล็อกนี้

การจัดเรียงแบบ Quick Sort

รูปภาพ
Quick Sort การจัดเรียงข้อมูลแบบ Quick Sort มีขั้นตอน 4 ขั้นคือ 1.       ถ้าจำนวนตัวเลขมีเพียง 0 หรือ 1 ตัวไม่ต้องทำงาน ให้หยุดทำได้ 2.       เลือกตัวเลขขึ้นมาหนึ่งตัว เรียกเลขตัวนี้ว่า Pivot สมมุติว่าคือ v 3.       แบ่งกลุ่มตัวเลขออกเป็น 2 กลุ่ม โดยกลุ่มที่ 1 จะต้องเป็นเลขที่น้อยกว่า v ทั้งหมด และกลุ่มที่ 2 จะต้องเป็นเลขที่มากกว่า v ทั้งหมด 4.       กลับไปที่ขั้นตอนที่ 1 ใหม่ โดยทำกับเลข กลุ่มที่ 1 และทำกับเลขกลุ่มที่ 2 ทำแบบนี้ไปเรื่อยๆ จนเลขในกลุ่มย่อยๆ ลดเหลือเพียงแค่ 0 หรือ 1 ตัวก็หยุดได้ ตัวอย่างการทำ Quick Sort เช่น ถ้ามีเลขอยู่ 10 ตัวอยู่ในอะเรย์ a ดังนี้ ถ้าจะจัดเรียงแบบ Quick Sort เราจะต้องหา Pivot ก่อนวิธีการหา Pivot ที่ไม่แนะนำคือ o     ใช้เลขตัวแรกสุดเป็น Pivot แบบนี้เสี่ยงในกรณีที่เลขในชุดนั้นจัดเรียงไว้เรียบร้อยแล้วจะได้ O(N 2 ) o     ใช้วิธีสุ่มเลขแบบ Random มีข้อเสียคือ อัลกอริธึมการสร้างเลขสุ่มเสียเวลาค่อนข้างนาน เราจะเลือก Pivot โดยใช้วิธี Median-of-Threee คือเลือกเลขตัวที่ 1 ตัวสุดท้าย และตัวตรงกลางขึ้นมา และหาค่า Median ของเลข 3 ตัวนี้ เช่นใ
อ่านเพิ่มเติม

กราฟอัลกอริธึม

รูปภาพ
กราฟอัลกอริธึม กราฟประกอบด้วยเซ็ตของจุดและด้าน จุดคือ Vertice และด้านคือ Edge เขียนในลักษณะเซ็ตของคณิตศาสตร์ได้เป็น G = (V, E) โดยสมมุติว่า G คือกราฟ 1 ตัว และ V คือ เซ็ตของ Vertice ส่วน E คือเซ็ตของ Edge รูปภาพ 1 ตัวอย่างของ Set G ที่ใช้แทนกราฟ สังเกตว่าเซ็ต E จะเป็นคู่อันดับ (Ordered Pair) ของ Vectice 2 ตัว เช่น (a, b) หมายถึงเส้นที่เชื่อมระหว่าง a ไป b ดังนั้นกล่าวได้ว่าคู่อันดับ (v, w) โดย v และ w ทุกตัวต้องเป็นสมาชิกของ V หรือเขียนแบบคณิตศาสตร์ได้เป็น (v, w) Î V บางครั้งเราจะเรียก edge ว่าเป็น arc ถ้าคู่อันดับมีการจัดเรียงกันมาตามลำดับและมีทิศทาง (directed) กราฟแบบที่แต่ละเส้นมีทิศทางกำกับไว้ เราจะเรียกว่า Directed Graph หรือย่อๆคือ digraphs สมมุติว่ามีจุดมุม Vertex อยู่จุดหนึ่ง ชื่อว่า w เราบอกว่าจุด w นี้ต่อติด (adjacent) กับจุด v ก็ต่อเมื่อ (w, v) Î E แต่ถ้ากราฟนี้เป็นแบบไม่มีทิศทาง เส้น (w, v) ย่อมเทียบเท่ากับเส้น (v, w) ดังนั้นถ้า w adjacent to v ดังนั้น v ก็ย่อมจะ adjacent to w ด้วย หรือพูดง่ายๆก็คือมันต่อติดกันทั้งขาไปและขากลับเพราะไม่สนใ
อ่านเพิ่มเติม

Huffman's Code

รูปภาพ
Huffman’s Code สมมุติว่าเราต้องการบีบอัดไฟล์ข้อมูล (compression) เช่นพวก zip ไฟล์ ปกติแล้วเราจะเปลี่ยนตัวอักษรที่อยู่ในไฟล์ให้กลายเป็นบิตข้อมูล (bit) ที่มีขนาดเล็กกว่าบิตข้อมูลธรรมดา เช่น ปกต ิเลข 5 อาจจะเป็นตัวเลข 0000 0101 ถ้าเก็บแบบ 8 บิต แต่ถ้าเราบีบอัดแล้วอาจจะใช้ที่เก็บจริงๆแค่ 3 บิตคือ 101 เท่านั้น เช่นถ้าในไฟล์เรามีข้อมูลตัวอักษร a, e, i, s, t, space bar, new line (สำหรับ space bar ก็คือช่องไฟ และ new line คือ ขึ้นบรรทัดใหม่ พวกนี้เป็นตัวอักษรล่องหน มองไม่เห็น แต่กินพื้นที่ไฟล์ด้วยเช่นกัน) เราต้องการบีบอัดไฟล์นี้ให้มีขนาดเล็กเราอาจจะเปลี่ยนตัวอักษรเหล่านี้ให้กลายเป็นรหัสขนาด 3 บิต ดังตารางต่อไปนี้ จากตารางข้างต้น สมมุติว่าในไฟล์มีข้อมูลดังนี้ aaeeiiissttt  a  ti เราสามารถแปลงให้กลายเป็นรหัสตามที่กำหนดไว้ได้ดังนี้ 000 000 001 001 010 010 010 011 011 100 100 100 110 000 101 101 100 010 เมื่อนับจำนวนบิตดูจะพบว่ามีขนาดทั้งหมด เท่ากับ 18 x 3 = 54 บิต สมมุติว่าถ้าในไฟล์มีตัว a อยู่ 10 ตัว ตัว e อยู่ 15 ตัว ตัว i อยู่ 12 ตัว ตัว s อยู่ 3 ตัว ตัว t อยู่ 4 ตั
อ่านเพิ่มเติม