ฮีปที่ผสานได้
ในวิทยาการคอมพิวเตอร์ฮีปที่ผสานได้ (หรือเรียกว่าฮีปที่หลอมรวมได้ ) เป็นชนิดข้อมูลนามธรรมซึ่งเป็นฮีปที่รองรับการดำเนินการผสาน
คำนิยาม
ฮีปที่ผสานได้รองรับการดำเนินการฮีปทั่วไป: [ 1 ]
Make-Heap()สร้างกองว่างเปล่าInsert(H,x)แทรกองค์ประกอบxลงในฮีHปMin(H)ส่งคืนค่าต่ำสุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่Extract-Min(H)ดึงข้อมูลและส่งคืนองค์ประกอบที่เล็กที่สุด หรือNilหากไม่มีองค์ประกอบดังกล่าวอยู่ ให้คืนค่าว่าง
และอีกหนึ่งสิ่งที่แตกต่างออกไป: [ 1 ]
Merge(H1,H2)รวมองค์ประกอบของH1และH2เข้าไว้ในกองเดียวกัน
การนำไปใช้งานที่ไม่ซับซ้อน
การสร้างฮีปที่สามารถผสานได้นั้นทำได้ง่าย หากมีฮีปแบบง่ายๆ อยู่แล้ว:
Merge(H1,H2):
x ← Extract-Min(H2)while x ≠ NilInsert(H1, x)x ← Extract-Min(H2)
อย่างไรก็ตาม วิธีนี้อาจสิ้นเปลือง เพราะแต่ละคนExtract-Min(H)มักInsert(H,x)จะต้องดูแลรักษาพื้นที่กองขยะ นั้นด้วย ตนเอง
การนำไปใช้งานที่มีประสิทธิภาพมากขึ้น
ตัวอย่างของโครงสร้างข้อมูลฮีปที่สามารถผสานได้ ได้แก่:
สามารถดูรายการที่สมบูรณ์ยิ่งขึ้นพร้อมการเปรียบเทียบประสิทธิภาพได้ที่Heap (โครงสร้างข้อมูล) § การเปรียบเทียบขอบเขตทางทฤษฎีสำหรับรูปแบบต่างๆ
ในโครงสร้างฮีปที่สามารถผสานได้ส่วนใหญ่ การผสานเป็นการดำเนินการพื้นฐานที่การดำเนินการอื่นๆ ขึ้นอยู่กับ การแทรกทำได้โดยการผสานฮีปใหม่ที่มีองค์ประกอบเดียวเข้ากับฮีปที่มีอยู่เดิม การลบทำได้โดยการผสานโหนดลูกของโหนดที่ถูกลบ