กลับไปหน้าบทความ

อ่าน 1 นาที

ฮีปที่ผสานได้

ฮีป (โครงสร้างข้อมูล)

ในวิทยาการคอมพิวเตอร์ฮีปที่ผสานได้ (หรือเรียกว่าฮีปที่หลอมรวมได้ ) เป็นชนิดข้อมูลนามธรรมซึ่งเป็นฮีปที่รองรับการดำเนินการผสาน

ฮีปที่ผสานได้

ในวิทยาการคอมพิวเตอร์ฮีปที่ผสานได้ (หรือเรียกว่าฮีปที่หลอมรวมได้ ) เป็นชนิดข้อมูลนามธรรมซึ่งเป็นฮีปที่รองรับการดำเนินการผสาน

คำนิยาม

ฮีปที่ผสานได้รองรับการดำเนินการฮีปทั่วไป: [ 1 ]

  • Make-Heap()สร้างกองว่างเปล่า
  • Insert(H,x)แทรกองค์ประกอบxลงในฮีH
  • Min(H)ส่งคืนค่าต่ำสุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่
  • Extract-Min(H)ดึงข้อมูลและส่งคืนองค์ประกอบที่เล็กที่สุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่ ให้คืนค่าว่าง

และอีกหนึ่งสิ่งที่แตกต่างออกไป: [ 1 ]

  • Merge(H1,H2)รวมองค์ประกอบของH1และH2เข้าไว้ในกองเดียวกัน

การนำไปใช้งานที่ไม่ซับซ้อน

การสร้างฮีปที่สามารถผสานได้นั้นทำได้ง่าย หากมีฮีปแบบง่ายๆ อยู่แล้ว:

Merge(H1,H2):

  1. x ← Extract-Min(H2)
  2. while x ≠ Nil
    1. Insert(H1, x)
    2. x ← Extract-Min(H2)

อย่างไรก็ตาม วิธีนี้อาจสิ้นเปลือง เพราะแต่ละคนExtract-Min(H)มักInsert(H,x)จะต้องดูแลรักษาพื้นที่กองขยะ นั้นด้วย ตนเอง

การนำไปใช้งานที่มีประสิทธิภาพมากขึ้น

ตัวอย่างของโครงสร้างข้อมูลฮีปที่สามารถผสานได้ ได้แก่:

สามารถดูรายการที่สมบูรณ์ยิ่งขึ้นพร้อมการเปรียบเทียบประสิทธิภาพได้ที่Heap (โครงสร้างข้อมูล) § การเปรียบเทียบขอบเขตทางทฤษฎีสำหรับรูปแบบต่างๆ

ในโครงสร้างฮีปที่สามารถผสานได้ส่วนใหญ่ การผสานเป็นการดำเนินการพื้นฐานที่การดำเนินการอื่นๆ ขึ้นอยู่กับ การแทรกทำได้โดยการผสานฮีปใหม่ที่มีองค์ประกอบเดียวเข้ากับฮีปที่มีอยู่เดิม การลบทำได้โดยการผสานโหนดลูกของโหนดที่ถูกลบ

ดูเพิ่มเติม

ดึงข้อมูลมาจาก " https://en.wikipedia.org/w/index.php?title=Mergeable_heap&oldid=1223688607 "

สรุปเนื้อหา

ข้อมูลสำคัญจากบทความ

ข้อมูลสำคัญเกี่ยวกับ ฮีปที่ผสานได้

ในวิทยาการคอมพิวเตอร์ฮีปที่ผสานได้ (หรือเรียกว่าฮีปที่หลอมรวมได้ ) เป็นชนิดข้อมูลนามธรรมซึ่งเป็นฮีปที่รองรับการดำเนินการผสาน

คำนิยาม

ฮีปที่ผสานได้รองรับการดำเนินการฮีปทั่วไป: [ 1 ]

การนำไปใช้งานที่ไม่ซับซ้อน

การสร้างฮีปที่สามารถผสานได้นั้นทำได้ง่าย หากมีฮีปแบบง่ายๆ อยู่แล้ว:

การนำไปใช้งานที่มีประสิทธิภาพมากขึ้น

ตัวอย่างของโครงสร้างข้อมูลฮีปที่สามารถผสานได้ ได้แก่: