ฮีปสคิว

สคิวฮีพ (อังกฤษ: Skew Heap) หรือ Self-adjusting Heap เป็นฮีปแบบมีลำดับอย่างหนึ่ง ซึ่งอิมพลีเมนต์มาจาก ต้นไม้แบบทวิภาค ไม่มีข้อจำกัดด้านโครงสร้าง ทำให้ความสูงของต้นไม้อาจจะไม่เท่ากับ log n เสมอไป แต่มีประสิทธิภาพเป็น O(log n) ในแบบถัวเฉลี่ย สคิวฮีพมีข้อดีกว่าฮีพแบบทวิภาคหรือ ต้นไม้แบบทวิภาค ตรงที่การดำเนินการรวมฮีพ (merge) ทำได้เร็วกว่า จึงมีการนำการดำเนินการรวมฮีพมาใช้ในการดำเนินการอื่นๆของสคิวฮีพด้วย

การดำเนินการของสคิวฮีพ แก้

การรวมฮีพ แก้

แบบใช้ความสัมพันธ์เวียนเกิด แก้

เปรียบเทียบรากของฮีพทั้งสอง โดยถ้ารากของ H2 มีขนาดเล็กกว่า H1 ทำการสลับ H1 กับ H2 เราจะได้ว่า รากของ H1 มีขนาดเล็กกว่ารากของ H2
ถ้าลูกทางขวาของ H1 เป็น null เราจะให้ H2 เป็นลูกทางขวาของ H1 แต่ถ้า H1 ยังมีลูกทางขวาอยู่ ให้ลูกทางขวาของ H1 เกิดจากการรวม H2 กับต้นไม้ย่อยที่เป็นลูกทางขวาของ H1 โดยใช้ความสัมพันธ์เวียนเกิด
ทำการสลับลูกทางซ้ายและลูกทางขวาของ H1
ผลจากการรวมฮีพจะอยู่ใน H1

ขั้นตอนวิธีในการรวมฮีพแบบเวียนเกิด^[1]

              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

แบบไม่ใช้ความสัมพันธ์เวียนเกิด แก้

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

- หากรากของต้นไม้ย่อยที่สองจากขวาสุดมีลูกทางซ้ายสลับไปเป็นลูกทางขวา

- เชื่อมโยงรากของต้นไม้ย่อยขวาสุดเป็นลูกซ้ายต้นไม้ย่อยที่สองจากขวาสุด