हीप सॉर्ट

हीप सॉर्ट असल में सिलेक्शन सॉर्ट ही है, बस सबसे बड़ा मान ढूँढने का तरीका बेहतर है। यह बिना सॉर्ट हुए मानों को एक हीप में रखता है, यानी सूची के अंदर ही रखा एक ट्री, जिसमें सबसे बड़ा मान हमेशा सबसे ऊपर होता है। उसे निकालने और हीप को ठीक करने में पूरी सूची स्कैन करने के बजाय लगभग log n चरण लगते हैं।

बाइनरी ट्री के रूप में बना एक हीप, जिसके नीचे वही मान बार के रूप में हैं, और रूट पर रखा सबसे बड़ा मान अदला-बदली से सूची के अंत में जा रहा है
बाइनरी ट्री के रूप में बना एक हीप, जिसके नीचे वही मान बार के रूप में हैं, और रूट पर रखा सबसे बड़ा मान अदला-बदली से सूची के अंत में जा रहा है

सूची के अंदर एक ट्री

बाइनरी हीप ऐसा ट्री है जिसे पॉइंटर की ज़रूरत नहीं होती। जगह 0 रूट है, और जगह i के चाइल्ड जगह 2i + 1 और 2i + 2 हैं, इसलिए जगह 1 और 2 रूट के चाइल्ड हैं, जगह 3 से 6 अगला स्तर, और इसी तरह आगे। आख़िरी स्तर को छोड़कर हर स्तर भरा होता है, और आख़िरी स्तर बाएँ से भरता है। मैक्स-हीप में हर पैरेंट अपने चाइल्ड से कम से कम उतना बड़ा होता है, इसलिए सबसे बड़ा मान हमेशा रूट पर होता है।

नीचे खिसकाना

सारा काम एक ही ऑपरेशन करता है। किसी मान को नीचे खिसकाने के लिए उसकी तुलना उसके चाइल्ड से करें। अगर बड़ा चाइल्ड उस मान से बड़ा है, तो दोनों की अदला-बदली होती है, और उस मान की तुलना उसके नए चाइल्ड से होती है। यह तब रुकता है जब कोई चाइल्ड बड़ा न हो, या जब मान सबसे नीचे पहुँच जाए। चूँकि ट्री में लगभग log₂ n स्तर ही होते हैं, एक बार नीचे खिसकाने में ज़्यादा से ज़्यादा लगभग 2 log₂ n तुलनाएँ लगती हैं।

पहले हीप बनाएँ, फिर सॉर्ट करें

हीप बनाने के लिए आख़िरी पैरेंट से पीछे की ओर रूट तक, हर पैरेंट को नीचे खिसकाएँ। किसी पैरेंट के नीचे खिसकने से पहले उसके नीचे का सबट्री हीप बन चुका होता है। फिर सॉर्ट करें: रूट, यानी सबसे बड़े मान, की अदला-बदली हीप के आख़िरी मान से करें। वह मान अब अपनी अंतिम जगह पर है। हीप एक छोटा हो जाता है, और रूट पर आया मान उसे ठीक करने के लिए नीचे खिसकता है। एक मान बचने तक दोहराएँ।

एक उदाहरण

5, 1, 4, 2, 8 लें। हीप बनाते समय 1 नीचे खिसककर 8 के नीचे जाता है, फिर 5 नीचे खिसककर 8 के नीचे जाता है, जिससे 8, 5, 4, 2, 1 बनता है। अब 8 अदला-बदली से अंत में जाता है; 1 रूट पर आता है और 5 और 2 से आगे नीचे खिसकता है: 5, 2, 4, 1 | 8। फिर 5 अंत में जाता है और 1 नीचे खिसककर 4 से आगे जाता है: 4, 2, 1 | 5, 8। दो और दौर में सूची पूरी हो जाती है: 1, 2, 4, 5, 8, 12 तुलनाओं और 10 अदला-बदली के बाद।

ख़ूबियाँ और कमियाँ

हीप सॉर्ट में सबसे ख़राब स्थिति में भी n log n के अनुपात में समय लगता है, और इसे अतिरिक्त मेमोरी नहीं चाहिए। क्विकसॉर्ट धीमा होकर n² तक जा सकता है और मर्ज सॉर्ट को सूची जितना लंबा बफ़र चाहिए, इसलिए हीप सॉर्ट सुरक्षित विकल्प है: C++ स्टैंडर्ड लाइब्रेरी में इस्तेमाल होने वाला introsort, क्विकसॉर्ट के विभाजन बिगड़ने पर इसी पर चला जाता है। असली कंप्यूटरों पर यह आमतौर पर दोनों से धीमा होता है, क्योंकि यह सूची में दूर-दूर की जगहों के बीच कूदता है, और यह स्थिर नहीं है। J. W. J. Williams ने 1964 में बाइनरी हीप के साथ हीप सॉर्ट प्रकाशित किया।

ख़ुद आज़माएँ

ऐप खोलें और आगे दबाएँ। बार के ऊपर का ट्री हीप दिखाता है: नीचे खिसक रहे मान का अपना रंग होता है, जिस चाइल्ड से उसकी तुलना हो रही है वह हाइलाइट होता है, और हर अदला-बदली ट्री और बार दोनों में दिखती है। हीप बनने के बाद देखें कि रूट अदला-बदली से अंत में जाता है, हरा हो जाता है और ट्री से बाहर हो जाता है।

अक्सर पूछे जाने वाले प्रश्न

हीप सॉर्ट की टाइम कॉम्प्लेक्सिटी क्या है?

सबसे अच्छी, औसत और सबसे ख़राब, तीनों स्थितियों में O(n log n)। हीप बनाने में O(n) लगता है, और n − 1 बार निकालने में से हर एक में O(log n)। यह O(1) अतिरिक्त मेमोरी के साथ इन-प्लेस सॉर्ट करता है।

हीप सॉर्ट और सिलेक्शन सॉर्ट में क्या अंतर है?

दोनों बार-बार बचा हुआ सबसे बड़ा (या सबसे छोटा) मान लेते हैं। सिलेक्शन सॉर्ट उसे बिना सॉर्ट हुए हिस्से को पूरा स्कैन करके ढूँढता है, हर बार n तुलनाएँ। हीप सॉर्ट बिना सॉर्ट हुए हिस्से को हीप में रखता है, जहाँ सबसे बड़ा मान पहले से सबसे ऊपर होता है, और हीप ठीक करने में बस लगभग log n तुलनाएँ लगती हैं।

सॉर्टिंग के अलावा हीप का क्या उपयोग है?

प्रायोरिटी क्यू: हीप सबसे बड़ा (या सबसे छोटा) आइटम तुरंत देता है और लगभग log n चरणों में आइटम जोड़ने या हटाने देता है। शेड्यूलर, Dijkstra का शॉर्टेस्ट-पाथ एल्गोरिदम और इवेंट सिमुलेशन, सभी इसका इस्तेमाल करते हैं।

क्या हीप सॉर्ट स्थिर है?

नहीं। रूट को अंत में भेजने से मान लंबी दूरी तय करते हैं, इसलिए बराबर मानों का आपसी क्रम बदल सकता है।

आज़माने के लिए तैयार?

अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।

हीप सॉर्ट आज़माएँ