ซอฟต์ฮีปคืออะไร?
ซอฟต์ฮีป (Soft Heap) เป็นโครงสร้างข้อมูลแบบฮีปที่ปรับแต่งจากฮีปทั่วไป โดยมีลักษณะพิเศษคือให้เวลาการทำงานแบบ amortized constant time (เวลาคงที่แบบเฉลี่ย) สำหรับ 5 การดำเนินการหลัก ซึ่งบรรลุได้โดยการ "ทำลาย" (Corrupt) หรือเพิ่มค่าคีย์ของจำนวนองค์ประกอบบางส่วนในฮีปอย่างระมัดระวัง
การดำเนินการ 5 แบบที่มีเวลาคงที่
- create(s) – สร้างซอฟต์ฮีปใหม่ s
- insert(s, y) – แทรกองค์ประกอบ y เข้าไปในซอฟต์ฮีป s
- meld(s, s') – รวมซอฟต์ฮีปสองตัว s และ s' ให้เป็นอันเดียว (ทั้งสองตัวถูกทำลาย)
- delete(s, y) – ลบองค์ประกอบ y ออกจากซอฟต์ฮีป s
- findmin(s) – ค้นหาองค์ประกอบที่มีคีย์น้อยที่สุดในซอฟต์ฮีป s
การเปรียบเทียบกับฮีปแบบอื่น
ฮีปแบบอื่น เช่น ฟีโบนัชชีฮีป (Fibonacci Heap) สามารถทำให้การดำเนินการส่วนใหญ่มีขีดจำกัดเวลาเท่าเดิม โดยไม่ต้องทำลายคีย์ แต่ไม่สามารถให้ขีดจำกัดเวลาคงที่สำหรับการดำเนินการ delete ที่สำคัญได้
การควบคุมการทำลายคีย์
ปริมาณการทำลายคีย์สามารถควบคุมได้โดยพารามิเตอร์ ε (อีพซิลอน) ซึ่งอยู่ระหว่าง 0 ถึง 1/2 อย่างไรก็ตาม ยิ่งตั้งค่า ε ให้น้อย ยิ่งทำให้การแทรก (insert) ใช้เวลานานขึ้น โดยเฉพาะ O(log 1/ε) สำหรับอัตราข้อผิดพลาด ε
ประกันของซอฟต์ฮีป
สำหรับค่า ε ที่คงที่ระหว่าง 0 ถึง 1/2 ในเวลาใดเวลาหนึ่ง จะมีคีย์ที่ถูกทำลายสูงสุด ε × m คีย์ โดยที่ m คือจำนวนองค์ประกอบที่ถูกแทรกหรือถูกทำลายไปแล้ว
ข้อจำกัดสำคัญ:
- ไม่สามารถรับประกันได้ว่าเพียงสัดส่วนคงที่ของคีย์ ที่อยู่ในฮีปอยู่แล้ว จะถูกทำลายหรือเพิ่มขึ้น: ในลำดับการแทรกและลบที่ไม่พึงประสงค์ อาจเกิดขึ้นว่าองค์ประกอบทั้งหมดในฮีปจะมีคีย์ที่เพิ่มขึ้นหรือถูกทำลายทั้งหมด
- ในลำดับขององค์ประกอบที่ถูกดึงออกมาจากฮีปด้วย findmin และ delete ไม่มีประกันว่าจะมีเพียงสัดส่วนคงที่ที่มีคีย์เสียหาย: ในสถานการณ์ที่โชคร้าย อาจดึงเฉพาะองค์ประกอบที่ถูกทำลายเท่านั้น
ประโยชน์และการประยุกต์ใช้
แม้จะมีข้อจำกัดและลักษณะที่ไม่สามารถคาดการณ์ได้ล่วงหน้า ซอฟต์ฮีปก็ยังมีประโยชน์ในการออกแบบ อัลกอริทึมเชิงกำหนด (Deterministic Algorithms) โดยเฉพาะ:
- ใช้เพื่อให้ได้ความซับซ้อนที่ดีที่สุดจนถึงปัจจุบันสำหรับการหา Minimum Spanning Tree (MST)
- สามารถนำไปสร้าง อัลกอริทึมการคัดเลือกที่เหมาะสม (Optimal Selection Algorithm)
- ใช้ใน อัลกอริทึมการจัดเรียงเกือบถูกต้อง (Near-sorting Algorithms) ซึ่งวางองค์ประกอบแต่ละตัวใกล้ตำแหน่งสุดท้ายของมัน – สถานการณ์ที่ Insertion Sort ทำงานได้รวดเร็ว
