ฮีปสคิว

สคิวฮีพ () หรือ 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

ขั้นตอนวิธีในการรวมฮีพแบบเวียนเกิด
               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

ขั้นตอนที่ 2

ขั้นตอนที่ 3

ขั้นตอนที่ 4

ขั้นตอนที่ 5

ขั้นตอนที่ 6

ขั้นตอนที่ 7

 การเพิ่ม 
 จะทำการรวมฮีพที่เราต้องการเพิ่มโหนดกับฮีพที่มีโหนดตัวที่เราต้องการเพิ่มอยู่เพียงโหนดเดียว

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

 อ้างอิง 

 แหล่งข้อมูลอื่น 
 CSE 4101 lecture notes, York University

หมวดหมู่:ฮีป (โครงสร้างข้อมูล)
หมวดหมู่:ต้นไม้แบบทวิภาค