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

สคริว ฮีพ

(Skew Heap)

            สคริวฮีพ เป็นต้นไม้ไบนารีที่เรียงลำดับแบบฮีพ และต้นไม้ในฮีพจะไม่มีข้อจำกัดในด้านโครงสร้าง
นิยาม โหนด p จะเป็นโหนดเฮฟวี่ (heavy) ถ้าจำนวนลูก ๆ ทางขวาของโหนด p มีจำนวนอย่างน้อยครึ่งหนึ่งของจำนวนลูกทั้งหมดของโหนด p ในทางกลับกัน ถ้าจำนวนลูก ๆ ทางซ้ายของโหนด p มีจำนวนอย่างน้อยครึ่งหนึ่งของจำนวนลูกทั้งหมดของโหนด p แล้วโหนด p จะเป็นโหนดไลท์ (light)
            ในการวิเคราะห์แบบถัวเฉลี่ยจะใช้วิธีศักย์ โดยให้ฟังก์ชันศักย์เป็นสัดส่วนโดยตรงกับจำนวนโหนดเฮฟวี่

การปฏิบัติการของสคริว ฮีพ

  1. การรวมฮีพ     การรวมของ 2 สคริวฮีพ ทำได้โดย
    1. ให้ฮีพหนึ่งไล่รวมจากบนลงล่างไปตามส่วนทางขวาของต้นไม้ในอีกฮีพหนึ่ง โดยให้มีการเรียงลำดับ
    2. ทำการสลับส่วนทางขวาให้ไปอยู่ทางซ้าย และส่วนทางซ้ายให้ไปอยู่ส่วนทางขวา โดยไล่สลับจากล่างขึ้นบนไปตามส่วนทางขวาของต้นไม้ ยกเว้นโหนดขวาสุด ไม่ต้องสลับเพราะจะเป็นโหนดที่ไม่มีลูกทางขวาให้สลับ
                เนื่องจากสคริวฮีพเป็นต้นไม้ที่ไม่มีข้อจำกัดในด้านโครงสร้าง จึงเป็นไปได้ที่ทุกๆโหนดในฮีพเอียงไปอยู่ทางด้านขวาของต้นไม้ กรณีนี้ถือเป็นกรณีร้ายแรงสุดที่เวลาที่ใช้ในการรวมฮีพ เป็น O(n) ในการวิเคราะห์ถัวเฉลี่ย สมมติให้ H1 และ H2 เป็นฮีพที่มี n1 และ n2 โหนดตามลำดับ โดยสมมติว่า H1 มีโหนดไลท์อยู่ทางขวา i1 โหนด และมีโหนด เฮฟวี่ อยู่ทางขวาเช่นกัน h1 โหนด และ h2 มีโหนด ไลท์ อยู่ทางขวา i2 โหนด และมีโหนด เฮฟวี่ อยู่ทางขวาเช่นกัน h2 โหนด นั่นคือ ต้นทุนจริงของการรวม เป็น i1+i2+h1+h2      ในส่วนทางขวา ถ้าโหนดใดเป็นโหนดเฮฟวี่แล้วหลังจากการรวม โหนดนั้นจะกลายเป็นโหนดไลท์ ส่วนโหนดอื่นๆที่เป็นโหนดไลท์หลังจากการรวมแล้วโหนดนั้นอาจจะเป็นหรือไม่เป็นโหนดเฮฟวี่ก็ได้ แต่ในกรณีร้ายแรงสุดโหนดที่เป็นโหนดไลท์\หลังจากการรวมแล้วกลายเป็นโหนดเฮฟวี่ ซึ่งจะเป็นการเพิ่มฟังก์ชันศักย์ นั่นคือจำนวนของโหนดเฮฟวี่ จะเพิ่มขึ้นเป็น i1+i2-h1-h2 ดังนั้น ต้นทุนที่ถัวเฉลี่ยแล้วเป็น (i1+i2+h1+h2) + (i1+i2-h1-h2) = 2(i1+i2) และเนื่องจาก i1 และ i2 เป็นจำนวนโหนดไลท์ในส่วนทางขวา และในจำนวนโหนดไลท์จะมีจำนวนโหนดน้อยกว่าครึ่งหนึ่งของจำนวนโหนดทั้งหมด ดังนั้น i1+i2 = log n1 + log n2 นั่นคือเวลาที่ใช้ในการรวมเป็น O(log n)
    อัลกอริทึมการรวมฮีพ เป็นดังนี้

MERGE (H1, H2)
// H1 and H2 are skew heaps
// Merge returns the merged heap, destroying H1 and H2
if H1 is empty
then return H2
else if H2 is empty then return H1
if the root of H2 < the root of H1 then swap H1 and H2
// now root(H1) < root(H2)
if right(H1) = nil
then right(H1) <-- (H2)
else right(H1) <-- Merge(right(H1), H2)
swap left and right children of H1
return H1

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

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

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

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

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