- नीचे खिसक रहा
- तुलना में
- बदले गए
- अपनी जगह पर
हीप सॉर्ट
हीप सॉर्ट सूची को बाइनरी ट्री की तरह पढ़ता है और उसे मैक्स-हीप में बदल देता है, जिसमें हर पैरेंट अपने चाइल्ड से कम से कम उतना बड़ा होता है। तब सबसे बड़ा मान सबसे ऊपर होता है। उसे अदला-बदली करके अंत में भेजें, जहाँ वह टिका रहता है, हीप को ठीक करें, और दोहराएँ। ऐप बार के ऊपर हीप को ट्री के रूप में दिखाता है, ताकि आप हर मान को नीचे खिसकते हुए देख सकें। सॉर्ट देखने के लिए चलाएँ दबाएँ, या एक-एक तुलना करके बढ़ने के लिए आगे और पीछे दबाएँ। कहीं भी जाने के लिए चरण स्लाइडर खींचें। बार के ऊपर का ट्री उन्हीं मानों को हीप के रूप में दिखाता है। टाइलें तुलनाएँ, अदला-बदली और हीप से निकाले गए मान गिनती हैं। बार की संख्या और उनका शुरुआती क्रम चुनें, या अपनी संख्याएँ लिखें। बोर्ड चुना हो तो तीर कुंजियाँ एक-एक चरण चलाती हैं, स्पेस बार चलाता और रोकता है, और Home व End शुरुआत और अंत पर ले जाते हैं।
यह कैसे काम करता है
- बार की संख्या और उनका शुरुआती क्रम चुनें: रैंडम, लगभग सॉर्ट, उल्टा, या कुछ ही अलग मानों वाला। या अपनी संख्याएँ लिखें।
- चलाएँ दबाएँ, या एक-एक तुलना करके बढ़ने के लिए आगे और पीछे का इस्तेमाल करें। सॉर्ट में कहीं भी जाने के लिए चरण स्लाइडर खींचें।
- ट्री को देखें: पहले हर पैरेंट नीचे खिसकता है जब तक हीप न बन जाए, फिर रूट की अदला-बदली अंत से होती है और हीप एक छोटा हो जाता है।
हीप सॉर्ट कैसे काम करता है
सूची को ट्री की तरह पढ़ें: जगह i वाले मान के चाइल्ड जगह 2i + 1 और 2i + 2 पर होते हैं। आख़िरी पैरेंट से शुरू करके हर पैरेंट को नीचे खिसकाकर मैक्स-हीप बनाएँ: जब तक कोई मान अपने बड़े चाइल्ड से छोटा है, दोनों की अदला-बदली होती है। जब रूट पर सबसे बड़ा मान हो, तो उसकी अदला-बदली हीप के आख़िरी मान से करें। वह मान अब पक्का है, हीप एक छोटा हो जाता है, और नया रूट नीचे खिसककर उसे फिर से हीप बनाता है। हीप ख़ाली होने तक दोहराएँ।
हमेशा n log n, इन-प्लेस
ट्री में लगभग log₂ n स्तर होते हैं, इसलिए हर बार नीचे खिसकाने में ज़्यादा से ज़्यादा लगभग 2 log₂ n तुलनाएँ लगती हैं, और हीप बनाने में 2n से कम। इसलिए हीप सॉर्ट की सबसे ख़राब स्थिति लगभग 2n log₂ n तुलनाएँ है, बिना किसी बफ़र के: 40 मानों के लिए ज़्यादा से ज़्यादा 352। क्विकसॉर्ट के उलट इसके लिए कोई बुरा इनपुट नहीं होता, और मर्ज सॉर्ट के उलट इसे अतिरिक्त मेमोरी नहीं चाहिए। व्यवहार में यह आमतौर पर दोनों से धीमा होता है, क्योंकि यह सूची में इधर-उधर कूदता है, और यह स्थिर नहीं है।
अक्सर पूछे जाने वाले प्रश्न
हीप सॉर्ट कैसे काम करता है?
यह सूची को मैक्स-हीप में बदलता है, यानी सूची में रखा एक ट्री जिसमें हर पैरेंट अपने चाइल्ड से कम से कम उतना बड़ा होता है। फिर यह बार-बार रूट पर रखे सबसे बड़े मान को हीप के अंत में भेजता है और हीप को ठीक करने के लिए नए रूट को नीचे खिसकाता है।
हीप क्या है?
सूची में बिना पॉइंटर के रखा एक पूर्ण बाइनरी ट्री: जगह i के चाइल्ड जगह 2i + 1 और 2i + 2 हैं। मैक्स-हीप में हर पैरेंट अपने चाइल्ड से कम से कम उतना बड़ा होता है, इसलिए सबसे बड़ा मान हमेशा रूट पर, यानी जगह 0 पर होता है।
हीप बनाना तेज़ क्यों है?
ज़्यादातर मान ट्री के निचले हिस्से में होते हैं और बस एक-दो स्तर ही नीचे खिसक सकते हैं। सभी स्तरों का काम जोड़ने पर पूरा हीप बनाने में n log n नहीं, बल्कि 2n से कम तुलनाएँ लगती हैं।
क्या हीप सॉर्ट स्थिर है?
नहीं। रूट को अंत में भेजने से मान लंबी दूरी तय करते हैं, इसलिए बराबर मानों का क्रम बदल सकता है।
क्या मेरी संख्याएँ कहीं भेजी जाती हैं?
नहीं। सॉर्ट आपके ब्राउज़र में चलता है, और आपकी पिछली सेटिंग्स इसी ब्राउज़र के लोकल स्टोरेज में रहती हैं।
आज़माने के लिए तैयार?
अपने ब्राउज़र में PictorX खोलें — शुरू करने के लिए इंस्टॉल या क्रेडिट कार्ड की ज़रूरत नहीं।
एडिटर पर जाएँ