সফ্ট হিপ হল একটি সাধারণ হিপ ডেটা স্ট্রাকচারের পরিবর্তনশীল রূপ যাতে ৫ ধরনের অপারেশন জন্য কনস্ট্যান্ট অ্যামোর্টাইজড টাইম অর্জন করা যায়। এটি হিপে নির্দিষ্ট সংখ্যক ভ্যালুর কী "দূষিত" (বৃদ্ধি) করার মাধ্যমে কাপড়ে পাওয়া যায়। কনস্ট্যান্ট টাইম অপারেশনগুলো হল:
- create(s) - একটি নতুন সফ্ট হিপ s তৈরি করুন
- insert(s, y) - একটি উপাদান y কে একটি সফ্ট হিপ s-এ প্রবেশ করান
- meld(s, s') - দুটি সফ্ট হিপ s এবং s' কে একত্রিত করে একটি করে দিন, দুটোই ধ্বংস করুন
- delete(s, y) - একটি উপাদান y কে একটি সফ্ট হিপ s থেকে মুছুন
- findmin(s) - সফ্ট হিপ s-এ সবচেয়ে কম কীযুক্ত উপাদানটি পান
ফিবোনাচ্চি হিপের মতো অন্যান্য হিপ এই বাউন্ডের অধিকাংশ অর্জন করতে পারে কোনো দূষণ ছাড়াই, কিন্তু ক্রিটিক্যাল delete অপারেশনে কনস্ট্যান্ট-টাইম বাউন্ড দিতে পারে না। দূষণের পরিমাণ প্যারামিটার ε-র পছন্দ দ্বারা নিয়ন্ত্রণ করা যায়, কিন্তু এটি যত কম সেট করা হয়, ইনসারশন তত বেশি সময় নেয় (ε ত্রুটি হার জন্য O(log 1/ε))।
অধিক সুনির্দিষ্টভাবে, সফ্ট হিপ দ্বারা প্রদত্ত গ্যারান্টি হল: ০ এবং ১/২ এর মধ্যে একটি নির্দিষ্ট ε মান জন্য, যেকোনো সময় হিপে সর্বোচ্চ ε*m দূষিত কী থাকবে, যেখানে m হল ইনসার্ট করা বা দূষিত উপাদানগুলোর সংখ্যা। আমরা গ্যারান্টি দিতে পারি না যে শুধু একটি নির্দিষ্ট শতাংশ কী বর্তমানে হিপে দূষিত বা বেড়ানো থাকবে: অপ্রত্যাশিত ইনসারশন ও ডিলিশনের ক্রমে, হিপের সব উপাদানই বেড়ানো বা দূষিত কীযুক্ত হতে পারে। একইভাবে, findmin এবং delete দিয়ে হিপ থেকে উপাদান বের করার ক্রমে শুধু একটি নির্দিষ্ট শতাংশই দূষিত বা বেড়ানো কীযুক্ত উপাদান বের হবে এমন গ্যারান্টি নেই: দুরভাগে শুধু দূষিত বা বেড়ানো উপাদানই বের হতে পারে।
তাদের সীমাবদ্ধতা ও অনির্দিষ্ট প্রকৃতির باয়जूद, সফ্ট হিপ ডিটারমিনিস্টিক অ্যালগরিদম ডিজাইন করতে উপযোগী। এগুলো ন্যূনতম স্প্যানিং ট্রি নির্ধারণের জন্য আজ পর্যন্ত সেরা কমপ্লেক্সিটি অর্জনের জন্য বাস্তবায়ন করা হয়েছিল। এছাড়া এগুলো অপ্টিমাল সিলেকশন অ্যালগরিদম এবং नियর-সোর্টিং অ্যালগরিদম বানাতেও ব্যবহার করা যায়, যেগুলো প্রতিটি উপাদানকে তার চূড়ান্ত অবস্থানের কাছাকাছি নিয়ে যায়—একটি পরিস্থিতি যেখানে ইনসারশন সোর্ট দ্রুত কাজ করে।
