ढेर को 'आंशिक रूप से क्रमबद्ध' कहा जाता है, न कि 'आंशिक रूप से क्रमबद्ध'। शब्द 'सॉर्ट' का अर्थ है पूर्ण क्रम (पूर्ण छँटाई)। एक ढेर को आंशिक रूप से मनमाने ढंग से आदेश नहीं दिया जाता है। एक ढेर को आंशिक रूप से एक मानदंड (पैटर्न) के बाद क्रमबद्ध किया जाता है, जैसा कि नीचे दिखाया गया है।
तो, हीपसॉर्ट में दो चरण होते हैं: ढेर का निर्माण और ढेर के ऊपर से आदेशित तत्व निकालना। दूसरे चरण में, प्रत्येक निष्कर्षण के बाद, ढेर का पुनर्निर्माण किया जाता है। प्रत्येक पुनर्निर्माण मूल निर्माण प्रक्रिया से तेज है क्योंकि पुनर्निर्माण पिछले निर्माण से किया जाता है, जहां एक तत्व हटा दिया गया है। और इसके साथ ही, हीपसॉर्ट पूरी तरह से क्रमबद्ध सूची को छांटता है।
इस लेख का उद्देश्य संक्षेप में हीपसॉर्ट की व्याख्या करना है और फिर इसकी समय जटिलता उत्पन्न करना है (नीचे समय जटिलता का अर्थ देखें)। अंत में, C++ में कोडिंग की जाती है।
न्यूनतम ढेर
एक ढेर न्यूनतम ढेर या अधिकतम ढेर हो सकता है। एक अधिकतम-ढेर वह है जहां पहला तत्व उच्चतम तत्व है, और पूरे पेड़ या संबंधित सूची को आंशिक रूप से अवरोही क्रम में क्रमबद्ध किया जाता है। एक न्यूनतम ढेर वह है जहां पहला तत्व सबसे छोटा तत्व है, और पूरी सूची आंशिक रूप से आरोही क्रम में क्रमबद्ध है। इस लेख में, केवल न्यूनतम ढेर पर विचार किया गया है। नोट: ढेर के विषय में, एक तत्व को नोड भी कहा जाता है।
ढेर एक पूर्ण बाइनरी ट्री है। बाइनरी ट्री को एक सरणी (सूची) के रूप में व्यक्त किया जा सकता है; ऊपर से नीचे और बाएँ से दाएँ पढ़ें। मिन-हीप के लिए हीप गुण यह है कि एक पैरेंट नोड अपने दो बच्चों में से प्रत्येक से कम या बराबर होता है। एक अनियंत्रित सूची का एक उदाहरण है:
| 9 | 19 | 24 | 5 | 3 | ग्यारह | 14 | 22 | 7 | 6 | 17 | पंद्रह | शून्य | शून्य | शून्य |
| 0 | 1 | दो | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ग्यारह | 12 | 13 | 14 |
इस तालिका की पहली पंक्ति सरणी के तत्व हैं। दूसरी पंक्ति में शून्य-आधारित सूचकांक हैं। तत्वों की इस सूची को एक पेड़ के रूप में व्यक्त किया जा सकता है। पूर्ण बाइनरी ट्री बनाने के लिए अशक्त तत्वों को जोड़ा गया है। कड़ाई से बोलते हुए, अशक्त तत्व सूची (पेड़) का हिस्सा नहीं हैं। इस सूची में कोई आदेश नहीं है, इसलिए यह अभी ढेर नहीं है। ढेर संपत्ति के अनुसार, आंशिक आदेश होने पर यह ढेर बन जाएगा।
नोड्स और इंडेक्स के बीच संबंध
याद रखें, हीप कॉन्फ़िगरेशन (हीप प्रॉपर्टी) होने से पहले हीप एक पूर्ण बाइनरी ट्री है। पिछली सूची अभी तक ढेर नहीं है, क्योंकि तत्व ढेर संपत्ति का पालन नहीं करते हैं। न्यूनतम ढेर संपत्ति के अनुसार तत्वों को आंशिक क्रम में पुनर्व्यवस्थित करने के बाद यह ढेर बन जाता है। आंशिक क्रम को आंशिक क्रम के रूप में देखा जा सकता है (हालाँकि 'सॉर्ट' शब्द का अर्थ पूर्ण क्रम है)।
बाइनरी ट्री एक ढेर है या नहीं, पत्ती (अंतिम) नोड्स को छोड़कर, प्रत्येक माता-पिता के दो बच्चे होते हैं। प्रत्येक माता-पिता और उसके बच्चों के बीच अनुक्रमणिका के बीच एक गणितीय संबंध होता है। यह इस प्रकार है: यदि माता-पिता सूचकांक i पर हैं, तो बायां बच्चा सूचकांक पर है:
दो * मैं + 1और सही बच्चा सूचकांक में है:
दो * मैं + दोयह शून्य-आधारित अनुक्रमण के लिए है। और इसलिए, इंडेक्स 0 पर एक माता-पिता का बायां बच्चा इंडेक्स 2×0+1=1 पर है और उसका दायां बच्चा 2×0+2=2 पर है। सूचकांक 1 पर माता-पिता का बायां बच्चा सूचकांक 2×1+1=3 पर है और दायां बच्चा सूचकांक 2×1+2=4 पर है; और इसी तरह।
मिन-हीप प्रॉपर्टी के अनुसार, i पर माता-पिता 2i+1 पर बाएं बच्चे से कम या उसके बराबर है और 2i+2 पर दाएं बच्चे से कम या बराबर है।
ढेर
हीपिंग का अर्थ है ढेर बनाना। इसका अर्थ है किसी सूची (या संबंधित पेड़) के तत्वों को पुनर्व्यवस्थित करना ताकि वे ढेर संपत्ति को संतुष्ट कर सकें। ढेर प्रक्रिया के अंत में, सूची या पेड़ एक ढेर है।
यदि पिछली अवर्गीकृत सूची को ढेर कर दिया जाता है, तो यह बन जाएगी:
| 3 | 5 | ग्यारह | 7 | 6 | पंद्रह | 14 | 22 | 9 | 19 | 17 | 24 | शून्य | शून्य | शून्य |
| 0 | 1 | दो | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | ग्यारह | 12 | 13 | 14 |
नोट: सूची में 12 तत्व हैं, 15 नहीं। दूसरी पंक्ति में सूचकांक हैं। ढेर निर्माण प्रक्रिया में, तत्वों की जाँच की जानी थी, और कुछ की अदला-बदली की।
ध्यान दें कि सबसे छोटा और पहला तत्व 3 है। शेष तत्व आरोही लेकिन लहरदार तरीके से अनुसरण करते हैं। यदि 2i+1 और 2i+2 पदों पर बाएँ और दाएँ बच्चे प्रत्येक i पर माता-पिता से बड़े या बराबर हैं, तो यह एक न्यूनतम-ढेर है। यह पूर्ण क्रम या छँटाई नहीं है। ढेर संपत्ति के अनुसार यह आंशिक आदेश है। यहीं से हीप सॉर्ट का अगला चरण शुरू होता है।
समय जटिलता को ढेर करें
समय जटिलता कुछ कोड के सापेक्ष चलने का समय है। इसे उस कोड को पूरा करने के लिए मुख्य संचालन की संख्या के रूप में देखा जा सकता है। ढेर निर्माण के लिए अलग-अलग एल्गोरिदम हैं। सबसे कुशल और सबसे तेज़ लगातार सूची को दो से विभाजित करते हैं, नीचे से तत्वों की जाँच करते हैं, और फिर तत्वों की कुछ अदला-बदली करते हैं। मान लीजिए N सूची में व्यावहारिक तत्वों की संख्या है। इस एल्गोरिथ्म के साथ, मुख्य संचालन (स्वैपिंग) की अधिकतम संख्या एन है। ढेर करने के लिए समय जटिलता पूर्व में दी गई है:
हे ( एन )जहाँ n, N है और मुख्य संक्रियाओं की अधिकतम संभव संख्या है। इस संकेतन को बिग-ओ नोटेशन कहा जाता है। यह अपरकेस में O से शुरू होता है, उसके बाद कोष्ठक से। कोष्ठक के अंदर संभावित उच्चतम संक्रियाओं के लिए व्यंजक है।
याद रखें: यदि वही जोड़ा जा रहा है तो जोड़ गुणा हो सकता है।
हीपसॉर्ट चित्रण
पिछली क्रमबद्ध सूची का उपयोग हीपसॉर्ट को दर्शाने के लिए किया जाएगा। दी गई सूची है:
9 19 24 5 3 ग्यारह 14 22 7 6 17 पंद्रहसूची से उत्पादित न्यूनतम ढेर है:
3 5 ग्यारह 7 6 पंद्रह 14 22 9 19 17 24हीपसॉर्ट में पहला चरण उस ढेर का उत्पादन करना है जिसका उत्पादन किया गया है। यह आंशिक रूप से आदेशित सूची है। यह एक क्रमबद्ध (पूरी तरह से क्रमबद्ध) सूची नहीं है।
दूसरे चरण में कम से कम तत्व को हटाना शामिल है, जो कि पहला तत्व है, ढेर से, शेष ढेर को फिर से ढेर करना, और परिणामों में कम से कम तत्वों को निकालना। सबसे छोटा तत्व हमेशा पुन: ढेर किए गए ढेर में पहला तत्व होता है। तत्वों को हटाया नहीं जाता है और फेंक दिया जाता है। उन्हें हटाए जाने के क्रम में एक अलग सरणी में भेजा जा सकता है।
अंत में, नई सरणी में आरोही क्रम में सभी तत्वों को क्रमबद्ध (पूरी तरह से) क्रमबद्ध किया जाएगा; और अब केवल आंशिक रूप से आदेश नहीं दिया गया है।
दूसरे चरण में, पहली बात यह है कि 3 को हटाकर नई सरणी में रखें। परिणाम हैं:
3तथा
5 ग्यारह 7 6 पंद्रह 14 22 9 19 17 24पहले तत्व को निकालने से पहले शेष तत्वों को ढेर करना पड़ता है। शेष तत्वों का ढेर बन सकता है:
5 6 7 9 पंद्रह 14 22 ग्यारह 19 17 245 निकालने और नई सूची (सरणी) में जोड़ने से परिणाम मिलते हैं:
3 5तथा
6 7 9 पंद्रह 14 22 ग्यारह 19 17 24शेष सेट को ढेर करने से मिलेगा:
6 7 9 पंद्रह 14 22 ग्यारह 19 17 246 निकालने और नई सूची (सरणी) में जोड़ने से परिणाम मिलते हैं:
3 5 6तथा
7 9 पंद्रह 14 22 ग्यारह 19 17 24शेष सेट को ढेर करने से मिलेगा:
7 9 ग्यारह 14 22 पंद्रह 19 17 247 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7तथा
9 ग्यारह 14 22 पंद्रह 19 17 24शेष सेट को ढेर करना देता है:
9 ग्यारह 14 22 पंद्रह 19 17 249 निकालने और नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9तथा
ग्यारह 14 22 पंद्रह 19 17 24शेष सेट को ढेर करना देता है:
ग्यारह 14 17 पंद्रह 19 22 2411 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारहतथा
14 17 पंद्रह 19 22 24शेष सेट को ढेर करने से मिलेगा:
14 17 पंद्रह 19 22 2414 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14तथा
17 पंद्रह 19 22 24शेष सेट को ढेर करने से मिलेगा:
पंद्रह 17 19 22 2415 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14 पंद्रहतथा
17 19 22 24शेष सेट को ढेर करने से मिलेगा:
17 19 22 2417 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14 पंद्रह 17तथा
19 22 24शेष सेट को ढेर करने से मिलेगा:
19 22 2419 को निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14 पंद्रह 17 19तथा
22 24शेष सेट को ढेर करना देता है:
22 2422 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14 पंद्रह 17 19 22तथा
24शेष सेट को ढेर करना देता है:
2424 निकालने और इसे नई सूची में जोड़ने से परिणाम मिलते हैं:
3 5 6 7 9 ग्यारह 14 पंद्रह 17 19 22 24तथा
- - -ढेर सरणी अब खाली है। शुरुआत में इसके सभी तत्व अब नई सरणी (सूची) में हैं और क्रमबद्ध हैं।
हीपसॉर्ट एल्गोरिथम
हालाँकि पाठक ने पाठ्यपुस्तकों में पढ़ा होगा कि हीपसॉर्ट में दो चरण होते हैं, फिर भी हीपसॉर्ट को एक चरण के रूप में देखा जा सकता है, जो दिए गए सरणी को पुनरावृत्त रूप से सिकोड़ता है। इसके साथ, हीपसॉर्ट के साथ सॉर्ट करने के लिए एल्गोरिथ्म इस प्रकार है:
- क्रमबद्ध सूची को ढेर करें।
- ढेर के पहले तत्व को निकालें और इसे नई सूची के पहले तत्व के रूप में रखें।
- शेष सूची को ढेर करें।
- नए ढेर के पहले तत्व को निकालें और नई सूची के अगले तत्व के रूप में रखें।
- पिछले चरणों को क्रम में दोहराएं जब तक कि ढेर सूची खाली न हो। अंत में, नई सूची को क्रमबद्ध किया जाता है।
हीपसॉर्ट समय जटिलता उचित
हेपसॉर्ट के लिए समय जटिलता निर्धारित करने के लिए एक-चरण दृष्टिकोण का उपयोग किया जाता है। मान लें कि क्रमबद्ध करने के लिए 8 अवर्गीकृत तत्व हैं।
संचालन की संभावित अधिकतम संख्या को ढेर करने के लिए 8 तत्व है 8 .शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 7 तत्व है 7 .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 6 तत्व है 6 .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 5 तत्व है 5 .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 4 तत्व है 4 .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 3 तत्व है 3 .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन दो तत्व है दो .
शेष को ढेर करने के लिए संभावित अधिकतम संख्या में संचालन 1 तत्व है 1 .
संचालन की संभावित अधिकतम संख्या है:
8 + 7 + 6 + 5 + 4 + 3 + दो + 1 = 36संचालन की इन संख्याओं का औसत है:
36 / 8 = 4.5ध्यान दें कि पिछले चित्रण में अंतिम चार ढेर नहीं बदले, जब पहला तत्व हटा दिया गया था। पहले तत्व को हटा दिए जाने पर पिछले कुछ ढेर भी नहीं बदले। इसके साथ, मुख्य संचालन (स्वैपिंग) की एक बेहतर औसत संख्या 3 है न कि 4.5। तो, मुख्य परिचालनों की एक बेहतर कुल औसत संख्या है:
24 = 8 एक्स 3=> 24 = 8 एक्स लकड़ी का लट्ठा < विषय > दो < / विषय > 8
लॉग के बाद से दो 8 = 3.
सामान्य तौर पर, हेपसॉर्ट के लिए औसत मामला समय जटिलता है:
हे ( एन। log2n )जहां डॉट का अर्थ है गुणा और n एन है, सूची में तत्वों की कुल संख्या (या तो सूची)।
ध्यान दें कि पहले तत्व को निकालने के संचालन को नजरअंदाज कर दिया गया है। समय जटिलता के विषय पर, अपेक्षाकृत कम समय लेने वाले कार्यों को अनदेखा कर दिया जाता है।
C++ में कोडिंग
C++ की एल्गोरिथम लाइब्रेरी में एक make_heap () फंक्शन है। वाक्यविन्यास है:
टेम्पलेट < कक्षा रैंडम एक्सेस इटरेटर, कक्षा तुलना करना >कॉन्स्टेक्सप्र शून्य Make_heap ( RandomAccessIterator पहले, RandomAccessIterator अंतिम, तुलना करें ) ;
यह एक वेक्टर के पहले तत्व को अपने पहले तर्क के रूप में इंगित करने वाले इटरेटर को लेता है और फिर इटरेटर को अपने अंतिम तर्क के रूप में वेक्टर के अंत से परे इंगित करता है। पिछली अवर्गीकृत सूची के लिए, न्यूनतम ढेर प्राप्त करने के लिए सिंटैक्स का उपयोग निम्नानुसार किया जाएगा:
वेक्टर < पूर्णांक > वीटीआर = { 9 , 19 , 24 , 5 , 3 , ग्यारह , 14 , 22 , 7 , 6 , 17 , पंद्रह } ;वेक्टर < पूर्णांक > :: इटरेटर iterB = वीटीआर शुरू करना ( ) ;
वेक्टर < पूर्णांक > :: इटरेटर iterE = वीटीआर समाप्त ( ) ;
Make_heap ( iterB, iterE, ग्रेटर < पूर्णांक > ( ) ) ;
यह कोड एक वेक्टर सामग्री को न्यूनतम हीप कॉन्फ़िगरेशन में बदलता है। निम्नलिखित सी ++ वैक्टर में, दो सरणियों के बजाय दो वैक्टर का उपयोग किया जाएगा।
वेक्टर के पहले तत्व की प्रतिलिपि बनाने और वापस करने के लिए, वेक्टर सिंटैक्स का उपयोग करें:
कॉन्स्टेक्सप्र संदर्भ मोर्चा ( ) ;वेक्टर के पहले तत्व को निकालने और उसे फेंकने के लिए, वेक्टर सिंटैक्स का उपयोग करें:
कॉन्स्टेक्सप्र इटरेटर मिटा ( const_iterator स्थिति )वेक्टर (अगला तत्व) के पीछे एक तत्व जोड़ने के लिए, वेक्टर सिंटैक्स का उपयोग करें:
कॉन्स्टेक्सप्र शून्य पीछे धकेलना ( स्थिरांक टी और एक्स ) ;कार्यक्रम की शुरुआत है:
#शामिल करें#शामिल <एल्गोरिदम>
#शामिल करें <वेक्टर>
का उपयोग करते हुए नाम स्थान कक्षा ;
एल्गोरिथ्म और वेक्टर पुस्तकालय शामिल हैं। कार्यक्रम में अगला हीपसॉर्ट () फ़ंक्शन है, जो है:
शून्य ढेर बनाएं और छांटें ( वेक्टर < पूर्णांक > और पुराना वी, वेक्टर < पूर्णांक > और नयावी ) {यदि ( पुराना वी. आकार ( ) > 0 ) {
वेक्टर < पूर्णांक > :: इटरेटर iterB = पुराना वी. शुरू करना ( ) ;
वेक्टर < पूर्णांक > :: इटरेटर iterE = पुराना वी. समाप्त ( ) ;
Make_heap ( iterB, iterE, ग्रेटर < पूर्णांक > ( ) ) ;
पूर्णांक अगला = पुराना वी. सामने ( ) ;
पुराना वी. मिटा ( iterB ) ;
नया वी. पीछे धकेलना ( अगला ) ;
ढेर बनाएं और छांटें ( पुराना वी, नया वी ) ;
}
}
यह एक पुनरावर्ती कार्य है। यह C++ एल्गोरिथम लाइब्रेरी के make_heap() फंक्शन का उपयोग करता है। फ़ंक्शन परिभाषा में दूसरा कोड खंड हीप बिल्डिंग के बाद पुराने वेक्टर से पहला तत्व निकालता है और नए वेक्टर के लिए अगले तत्व के रूप में जोड़ता है। ध्यान दें कि फ़ंक्शन परिभाषा में, वेक्टर पैरामीटर संदर्भ हैं, जबकि फ़ंक्शन को पहचानकर्ताओं (नामों) के साथ कहा जाता है।
इसके लिए एक उपयुक्त C++ मुख्य कार्य है:
पूर्णांक मुख्य ( पूर्णांक आर्गसी, चारो ** अर्जीवी ){
वेक्टर < पूर्णांक > पुराना वी = { 9 , 19 , 24 , 5 , 3 , ग्यारह , 14 , 22 , 7 , 6 , 17 , पंद्रह } ;
वेक्टर < पूर्णांक > नयावी ;
ढेर बनाएं और छांटें ( पुराना वी, नया वी ) ;
के लिये ( पूर्णांक मैं = 0 ; मैं < नया वी. आकार ( ) ; मैं ++ ) {
अदालत << नयावी [ मैं ] << '' ;
}
अदालत << एंडली ;
वापसी 0 ;
}
आउटपुट है:
3 5 6 7 9 ग्यारह 14 पंद्रह 17 19 22 24क्रमबद्ध (पूरी तरह से)।
निष्कर्ष
लेख में हीप सॉर्ट की प्रकृति और कार्य के बारे में विस्तार से चर्चा की गई, जिसे आमतौर पर हीप्सोर्ट के रूप में जाना जाता है, एक सॉर्टिंग एल्गोरिदम के रूप में। Heapify Time Complexity, Heapsort चित्रण, और Heapsort को एक एल्गोरिथ्म के रूप में उदाहरणों द्वारा कवर और समर्थित किया गया था। एक अच्छी तरह से लिखे गए हीपसॉर्ट प्रोग्राम के लिए औसत समय जटिलता O(nlog(n)) है