ฮีปสคิว

จากวิกิพีเดีย สารานุกรมเสรี

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

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

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

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

  1. เปรียบเทียบรากของฮีพทั้งสอง โดยถ้ารากของ H2 มีขนาดเล็กกว่า H1 ทำการสลับ H1 กับ H2 เราจะได้ว่า รากของ H1 มีขนาดเล็กกว่ารากของ H2
  2. ถ้าลูกทางขวาของ H1 เป็น null เราจะให้ H2 เป็นลูกทางขวาของ H1 แต่ถ้า H1 ยังมีลูกทางขวาอยู่ ให้ลูกทางขวาของ H1 เกิดจากการรวม H2 กับต้นไม้ย่อยที่เป็นลูกทางขวาของ H1 โดยใช้ความสัมพันธ์เวียนเกิด
  3. ทำการสลับลูกทางซ้ายและลูกทางขวาของ H1
  4. ผลจากการรวมฮีพจะอยู่ใน 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

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

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

ขั้นตอนที่ 1

ขั้นตอนที่ 2

ขั้นตอนที่ 3

ขั้นตอนที่ 4

ขั้นตอนที่ 5

ขั้นตอนที่ 6

ขั้นตอนที่ 7

การเพิ่ม[แก้]

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

การลบโหนดที่มีค่าน้อยที่สุด[แก้]

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

อ้างอิง[แก้]

แหล่งข้อมูลอื่น[แก้]