सॉफ्ट हीप एक प्रकार का डेटा स्ट्रक्चर है जो साधारण हीप का एक रूपांतर है और जिसमें 5 प्रकार के ऑपरेशन्स के लिए कॉन्स्टेंट एमोर्टाइज़्ड टाइम होता है। यह हीप में अधिकतम निश्चित संख्या में मानों की "करप्ट" (बढ़ी हुई) कीज़ को सावधानीपूर्वक मैनेज करके प्राप्त किया जाता है। कॉन्स्टेंट टाइम ऑपरेशन्स निम्नलिखित हैं:
- create(s) - एक नया सॉफ्ट हीप s बनाता है
- insert(s, y) - एक एलिमेंट y को सॉफ्ट हीप s में इन्सर्ट करता है
- meld(s, s') - दो सॉफ्ट हीप s और s' को एक में मिलाता है, दोनों को नष्ट करके
- delete(s, y) - एक एलिमेंट y को सॉफ्ट हीप s से डिलीट करता है
- findmin(s) - सॉफ्ट हीप s में सबसे कम की वाले एलिमेंट को प्राप्त करता है
फाइबोनैचि हीप जैसे अन्य हीप इनमें से अधिकांश बाउंड्स को बिना किसी करप्शन के प्राप्त करते हैं, लेकिन डिलीट ऑपरेशन पर कॉन्स्टेंट-टाइम बाउंड प्रदान नहीं कर सकते। करप्शन की मात्रा को पैरामीटर ε (0 और 1/2 के बीच) की पसंद द्वारा नियंत्रित किया जा सकता है, लेकिन यह जितना कम सेट किया जाता है, इन्सर्शन में उतना ही अधिक समय लगता है (ε त्रुटि दर के लिए O(log 1/ε))।
अधिक सटीक रूप से, सॉफ्ट हीप द्वारा दी जाने वाली गारंटी निम्नलिखित है: 0 और 1/2 के बीच एक निश्चित मान ε के लिए, किसी भी समय हीप में अधिकतम ε*m करप्ट कीज़ होंगी, जहाँ m इन्सर्ट किए गए या करप्ट किए गए एलिमेंट्स की संख्या है। हम यह गारंटी नहीं दे सकते कि वर्तमान में हीप में केवल एक निश्चित प्रतिशत कीज़ ही करप्ट या बढ़ी हुई हैं: अवांछित इन्सर्शन और डिलीशन के क्रम में, ऐसा हो सकता है कि हीप के सभी एलिमेंट्स की कीज़ बढ़ी हुई या करप्ट हों। इसी तरह, findmin और डिलीट का उपयोग करके हीप से निकाले गए एलिमेंट्स के क्रम में केवल एक निश्चित प्रतिशत के करप्ट या बढ़ी हुई कीज़ होने की कोई गारंटी नहीं है: एक दुर्भाग्यपूर्ण परिदृश्य में केवल करप्ट या बढ़े हुए एलिमेंट्स ही हीप से निकाले जा सकते हैं।
उनकी सीमाओं और अप्रत्याशित प्रकृति के बावजूद, सॉफ्ट हीप डिटरमिनिस्टिक एल्गोरिदम डिजाइन करने के लिए उपयोगी हैं। इनका उपयोग न्यूनतम स्पैनिंग ट्री निर्धारित करने के लिए अब तक की सर्वोत्तम जटिलता प्राप्त करने के लिए किया गया था। इनका उपयोग इष्टतम चयन एल्गोरिदम और नियर-सॉर्टिंग एल्गोरिदम बनाने के लिए भी किया जा सकता है, जो ऐसे एल्गोरिदम हैं जो प्रत्येक एलिमेंट को उसकी अंतिम स्थिति के निकट रखते हैं, एक ऐसी स्थिति जिसमें इन्सर्शन सॉर्ट तेज होता है।