ซอฟต์ฮีปถูกกำหนดให้เป็นรูปแบบของโครงสร้างข้อมูลฮีปอย่างง่ายที่ประกอบด้วยเวลาตัดจำหน่ายคงที่สำหรับการดำเนินการ 5 ประเภท สิ่งนี้ได้มาจากการ "ทำลาย" อย่างระมัดระวัง (เพิ่ม) คีย์ของค่าจำนวนหนึ่งในฮีปสูงสุด การดำเนินการเวลาคงที่คือ −
- สร้าง − สร้างซอฟต์ฮีปใหม่
- แทรก(s, y) − แทรกองค์ประกอบ y ลงใน soft heap s
- meld(s, s' ) ของสองกองอ่อนและ s′ เป็นหนึ่งเดียว ทำลายทั้งสองอย่าง
- ลบ(s, y) − ลบองค์ประกอบ y จาก soft heap s
- ค้นหาข้อมูล − รับองค์ประกอบที่มีคีย์น้อยที่สุดใน soft heap s
- ฮีปอื่นๆ เช่น ฮีป Fibonacci บรรลุขอบเขตส่วนใหญ่โดยไม่มีการทุจริตใดๆ แต่ไม่สามารถระบุการจำกัดเวลาคงที่ในการดำเนินการลบที่สำคัญได้ ปริมาณการทุจริตสามารถควบคุมได้โดยใช้พารามิเตอร์ ε แต่ยิ่งตั้งค่าไว้ต่ำ ยิ่งต้องใช้เวลามากขึ้น (O(บันทึก 1/ε) สำหรับอัตราข้อผิดพลาด ε)
- ให้แม่นยำยิ่งขึ้น การรับประกันที่เสนอโดยซอฟต์ฮีปมีดังต่อไปนี้:สำหรับค่าคงที่ ε ระหว่าง 0 ถึง 1/2 ณ เวลาใดเวลาหนึ่ง จะมีคีย์ที่เสียหายสูงสุด ε*m ในฮีป โดยที่ m คือ จำนวนองค์ประกอบที่แทรกหรือเสียหาย W เราไม่สามารถรับประกันได้ว่ามีเพียงเปอร์เซ็นต์คงที่ของคีย์ ปัจจุบัน ในฮีปเสียหายหรือเพิ่มขึ้น:ในการแทรกและการลบตามลำดับที่ไม่ต้องการ อาจเกิดขึ้นได้ว่าองค์ประกอบทั้งหมดในฮีปจะมีคีย์เพิ่มขึ้นหรือเสียหาย ในกรณีเดียวกัน ไม่มีการรับประกันว่าในลำดับขององค์ประกอบที่แยกจากฮีป กับ findmin และลบ มีเพียงเปอร์เซ็นต์คงที่เท่านั้นที่จะมีคีย์ที่เสียหายหรือเพิ่มขึ้น:ในสถานการณ์ที่โชคร้าย เฉพาะองค์ประกอบที่เสียหายหรือเพิ่มขึ้นเท่านั้นที่จะดึงออกมาจากฮีป
- แม้ว่าจะมีข้อจำกัดและลักษณะที่คาดเดาไม่ได้ แต่ soft heap ก็มีประโยชน์สำหรับการออกแบบอัลกอริทึมที่กำหนดขึ้นเอง พวกเขาถูกนำมาใช้เพื่อให้ได้ความซับซ้อนที่ดีที่สุดในปัจจุบันสำหรับการกำหนดต้นไม้ที่ทอดข้ามขั้นต่ำ นอกจากนี้ยังสามารถนำมาใช้เพื่อสร้างอัลกอริธึมการเลือกที่เหมาะสมที่สุด และอัลกอริธึมการเรียงลำดับใกล้เคียง ซึ่งเป็นอัลกอริธึมที่ตั้งค่าทุกองค์ประกอบใกล้กับตำแหน่งสุดท้าย ซึ่งเป็นสถานการณ์ที่การจัดเรียงการแทรกนั้นรวดเร็ว
