हीप (डेटा संरचना): Difference between revisions

From Vigyanwiki
No edit summary
No edit summary
Line 1: Line 1:
{{short description|Computer science data structure}}
{{short description|Computer science data structure}}
{{For|मेमोरी हीप (निम्न-स्तरीय कंप्यूटर प्रोग्रामिंग में), जिसका डेटा संरचना से कोई संबंध नहीं है|C डायनामिक मेमोरी आवंटन}}
{{For|मेमोरी हीप (निम्न-स्तरीय कंप्यूटर प्रोग्रामिंग में), जिसका डेटा संरचना से कोई संबंध नहीं है|C डायनामिक मेमोरी आवंटन}}
[[File:Max-Heap-new.svg|thumb|एक [[ बाइनरी वृक्ष ]] मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं]][[कंप्यूटर विज्ञान]] में, हीप एक विशेष [[वृक्ष ([[डेटा संरचना]])]]-आधारित डेटा संरचना है जो हीप संपत्ति को संतुष्ट करती है: ''अधिकतम हीप'' में, किसी दिए गए [[नोड (कंप्यूटर विज्ञान)]] सी के लिए, यदि पी मूल नोड है C, तो P की ''कुंजी'' ('मान'') C की कुंजी से अधिक या उसके बराबर है। एक ''न्यूनतम ढेर'' में, P की कुंजी, C की कुंजी से कम या उसके बराबर है सी की कुंजी<ref>Black (ed.), Paul E. (2004-12-14). Entry for ''heap'' in ''[[Dictionary of Algorithms and Data Structures]]''. Online version. U.S. [[National Institute of Standards and Technology]], 14 December 2004. Retrieved on 2017-10-08 from https://xlinux.nist.gov/dads/HTML/heap.html.</ref> ढेर के शीर्ष पर स्थित नोड (बिना माता-पिता के) को रूट नोड कहा जाता है।
[[File:Max-Heap-new.svg|thumb|एक [[ बाइनरी वृक्ष ]] मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं]][[कंप्यूटर विज्ञान]] में, हीप विशेष [[वृक्ष ([[डेटा संरचना]])]]-आधारित डेटा संरचना है जो हीप संपत्ति को संतुष्ट करती है: ''अधिकतम हीप'' में, किसी दिए गए [[नोड (कंप्यूटर विज्ञान)]] सी के लिए, यदि पी मूल नोड है C, तो P की ''कुंजी'' ('मान'') C की कुंजी से अधिक या उसके बराबर है। ''न्यूनतम ढेर'' में, P की कुंजी, C की कुंजी से कम या उसके बराबर है सी की कुंजी<ref>Black (ed.), Paul E. (2004-12-14). Entry for ''heap'' in ''[[Dictionary of Algorithms and Data Structures]]''. Online version. U.S. [[National Institute of Standards and Technology]], 14 December 2004. Retrieved on 2017-10-08 from https://xlinux.nist.gov/dads/HTML/heap.html.</ref> ढेर के शीर्ष पर स्थित नोड (बिना माता-पिता के) को रूट नोड कहा जाता है।


हीप एक [[अमूर्त डेटा प्रकार]] का अधिकतम कुशल कार्यान्वयन है जिसे [[प्राथमिकता कतार]] कहा जाता है, और वास्तव में, प्राथमिकता कतारों को अक्सर ढेर के रूप में संदर्भित किया जाता है, भले ही उन्हें कैसे भी लागू किया जा सकता है। एक ढेर में, उच्चतम (या निम्नतम) प्राथमिकता वाला तत्व हमेशा जड़ में संग्रहीत होता है। हालाँकि, ढेर एक क्रमबद्ध संरचना नहीं है; इसे आंशिक रूप से ऑर्डर किया गया माना जा सकता है। ढेर एक उपयोगी डेटा संरचना है जब उच्चतम (या निम्नतम) प्राथमिकता के साथ ऑब्जेक्ट को बार-बार हटाना आवश्यक होता है, या जब सम्मिलन को रूट नोड के निष्कासन के साथ जोड़ने की आवश्यकता होती है।
हीप [[अमूर्त डेटा प्रकार]] का अधिकतम कुशल कार्यान्वयन है जिसे [[प्राथमिकता कतार]] कहा जाता है, और वास्तव में, प्राथमिकता कतारों को अक्सर ढेर के रूप में संदर्भित किया जाता है, तथापि  उन्हें कैसे भी लागू किया जा सकता है। ढेर में, उच्चतम (या निम्नतम) प्राथमिकता वाला तत्व हमेशा जड़ में संग्रहीत होता है। हालाँकि, ढेर क्रमबद्ध संरचना नहीं है; इसे आंशिक रूप से ऑर्डर किया गया माना जा सकता है। ढेर उपयोगी डेटा संरचना है जब उच्चतम (या निम्नतम) प्राथमिकता के साथ ऑब्जेक्ट को बार-बार हटाना आवश्यक होता है, या जब सम्मिलन को रूट नोड के निष्कासन के साथ जोड़ने की आवश्यकता होती है।


ढेर का एक सामान्य कार्यान्वयन [[ बाइनरी ढेर ]] है, जिसमें पेड़ एक बाइनरी_ट्री#Types_of_binary_trees है<ref>{{Cite book|title=एल्गोरिदम का परिचय| last=CORMEN|first=THOMAS H.|publisher=The MIT Press Cambridge, Massachusetts London, England|year=2009| isbn=978-0-262-03384-8|location=United States of America|pages=151–152}}</ref> बाइनरी ट्री (चित्र देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जेडब्ल्यूजे विलियम्स द्वारा [[ढेर बनाएं और छांटें]] सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में पेश की गई थी।<ref>{{Citation |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi= 10.1145/512274.512284}}</ref> दिज्क्स्ट्रा के एल्गोरिदम जैसे कई कुशल [[ग्राफ एल्गोरिदम]] में भी हीप्स महत्वपूर्ण हैं। जब एक ढेर एक पूर्ण बाइनरी ट्री होता है, तो इसकी ऊंचाई सबसे छोटी होती है - एन नोड्स वाले ढेर और प्रत्येक नोड के लिए शाखाओं में हमेशा लॉग होता है<sub>''a''</sub> एन ऊंचाई.
ढेर का सामान्य कार्यान्वयन [[ बाइनरी ढेर ]] है, जिसमें पेड़ बाइनरी_ट्री#Types_of_binary_trees है<ref>{{Cite book|title=एल्गोरिदम का परिचय| last=CORMEN|first=THOMAS H.|publisher=The MIT Press Cambridge, Massachusetts London, England|year=2009| isbn=978-0-262-03384-8|location=United States of America|pages=151–152}}</ref> बाइनरी ट्री (चित्र देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जेडब्ल्यूजे विलियम्स द्वारा [[ढेर बनाएं और छांटें]] सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में पेश की गई थी।<ref>{{Citation |first=J. W. J. |last=Williams |author-link=J. W. J. Williams |title=Algorithm 232 - Heapsort |year=1964 |journal=[[Communications of the ACM]] |volume=7 |issue=6 |pages=347–348 |doi= 10.1145/512274.512284}}</ref> दिज्क्स्ट्रा के एल्गोरिदम जैसे कई कुशल [[ग्राफ एल्गोरिदम]] में भी हीप्स महत्वपूर्ण हैं। जब ढेर पूर्ण बाइनरी ट्री होता है, तो इसकी ऊंचाई सबसे छोटी होती है - एन नोड्स वाले ढेर और प्रत्येक नोड के लिए शाखाओं में हमेशा लॉग होता है<sub>''a''</sub> एन ऊंचाई.


ध्यान दें, जैसा कि ग्राफ़िक में दिखाया गया है, भाई-बहनों या चचेरे भाइयों के बीच कोई निहित आदेश नहीं है और [[इनऑर्डर ट्रैवर्सल]] के लिए कोई निहित अनुक्रम नहीं है (जैसा कि, उदाहरण के लिए, एक [[बाइनरी सर्च ट्री]] में होगा)। ऊपर उल्लिखित ढेर संबंध केवल नोड्स और उनके माता-पिता, दादा-दादी आदि के बीच लागू होता है। प्रत्येक नोड में बच्चों की अधिकतम संख्या ढेर के प्रकार पर निर्भर करती है।
ध्यान दें, जैसा कि ग्राफ़िक में दिखाया गया है, भाई-बहनों या चचेरे भाइयों के बीच कोई निहित आदेश नहीं है और [[इनऑर्डर ट्रैवर्सल]] के लिए कोई निहित अनुक्रम नहीं है (जैसा कि, उदाहरण के लिए, [[बाइनरी सर्च ट्री]] में होगा)। ऊपर उल्लिखित ढेर संबंध केवल नोड्स और उनके माता-पिता, दादा-दादी आदि के बीच लागू होता है। प्रत्येक नोड में बच्चों की अधिकतम संख्या ढेर के प्रकार पर निर्भर करती है।


==संचालन==
==संचालन==
Line 13: Line 13:
;बुनियादी
;बुनियादी
* फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ [[पीक (डेटा प्रकार ऑपरेशन)]])
* फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ [[पीक (डेटा प्रकार ऑपरेशन)]])
* सम्मिलित करें: ढेर में एक नई कुंजी जोड़ना (उर्फ, पुश)।<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappush heapq.heappush]</ref>)
* सम्मिलित करें: ढेर में नई कुंजी जोड़ना (उर्फ, पुश)।<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappush heapq.heappush]</ref>)
* एक्स्ट्रैक्ट-मैक्स (या एक्स्ट्रैक्ट-मिन): इसे हीप (उर्फ पॉप) से हटाने के बाद अधिकतम हीप [या मिन हीप से न्यूनतम मान] से अधिकतम मूल्य का नोड लौटाता है<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappop heapq.heappop]</ref>)
* एक्स्ट्रैक्ट-मैक्स (या एक्स्ट्रैक्ट-मिन): इसे हीप (उर्फ पॉप) से हटाने के बाद अधिकतम हीप [या मिन हीप से न्यूनतम मान] से अधिकतम मूल्य का नोड लौटाता है<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heappop heapq.heappop]</ref>)
* डिलीट-मैक्स (या डिलीट-मिन): क्रमशः अधिकतम हीप (या मिन हीप) के रूट नोड को हटाना
* डिलीट-मैक्स (या डिलीट-मिन): क्रमशः अधिकतम हीप (या मिन हीप) के रूट नोड को हटाना
* बदलें: रूट पॉप करें और एक नई कुंजी दबाएं। पॉप के बाद पुश की तुलना में अधिक कुशल, क्योंकि केवल एक बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के ढेर के लिए उपयुक्त।<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heapreplace heapq.heapreplace]</ref>
* बदलें: रूट पॉप करें और नई कुंजी दबाएं। पॉप के बाद पुश की तुलना में अधिक कुशल, क्योंकि केवल बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के ढेर के लिए उपयुक्त।<ref>The Python Standard Library, 8.4. heapq — Heap queue algorithm, [https://docs.python.org/2/library/heapq.html#heapq.heapreplace heapq.heapreplace]</ref>
;निर्माण
;निर्माण
* क्रिएट-हीप: एक खाली ढेर बनाएं
* क्रिएट-हीप: खाली ढेर बनाएं
* ढेर बनाना: तत्वों की दी गई श्रृंखला से एक ढेर बनाएं
* ढेर बनाना: तत्वों की दी गई श्रृंखला से ढेर बनाएं
* विलय (संघ): दो ढेरों को जोड़कर एक वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, मूल ढेर को संरक्षित करना।
* विलय (संघ): दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, मूल ढेर को संरक्षित करना।
* मेल्ड: दो ढेरों को जोड़कर एक वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, जिससे मूल ढेर नष्ट हो जाए।
* मेल्ड: दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, जिससे मूल ढेर नष्ट हो जाए।


;निरीक्षण
;निरीक्षण
Line 28: Line 28:


;आंतरिक
;आंतरिक
* वृद्धि-कुंजी या कमी-कुंजी: एक कुंजी को क्रमशः अधिकतम या न्यूनतम-ढेर के भीतर अद्यतन करना
* वृद्धि-कुंजी या कमी-कुंजी: कुंजी को क्रमशः अधिकतम या न्यूनतम-ढेर के भीतर अद्यतन करना
* हटाएं: एक मनमाना नोड हटाएं (इसके बाद अंतिम नोड को स्थानांतरित करें और ढेर बनाए रखने के लिए छान लें)
* हटाएं: मनमाना नोड हटाएं (इसके बाद अंतिम नोड को स्थानांतरित करें और ढेर बनाए रखने के लिए छान लें)
* सिफ्ट-अप: जब तक आवश्यक हो, पेड़ में एक नोड को ऊपर ले जाएं; सम्मिलन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है। इसे सिफ्ट कहा जाता है क्योंकि नोड पेड़ के ऊपर तब तक चलता रहता है जब तक कि यह सही स्तर तक नहीं पहुंच जाता, जैसे कि छलनी में।
* सिफ्ट-अप: जब तक आवश्यक हो, पेड़ में नोड को ऊपर ले जाएं; सम्मिलन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है। इसे सिफ्ट कहा जाता है क्योंकि नोड पेड़ के ऊपर तब तक चलता रहता है जब तक कि यह सही स्तर तक नहीं पहुंच जाता, जैसे कि छलनी में।
* सिफ्ट-डाउन: सिफ्ट-अप के समान, पेड़ में एक नोड को नीचे ले जाएं; हटाने या प्रतिस्थापन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है।
* सिफ्ट-डाउन: सिफ्ट-अप के समान, पेड़ में नोड को नीचे ले जाएं; हटाने या प्रतिस्थापन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है।


==कार्यान्वयन==
==कार्यान्वयन==
हीप्स को आमतौर पर एक [[सरणी डेटा संरचना]] के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:
हीप्स को आमतौर पर [[सरणी डेटा संरचना]] के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:


* सरणी में प्रत्येक तत्व ढेर के एक नोड का प्रतिनिधित्व करता है, और
* सरणी में प्रत्येक तत्व ढेर के नोड का प्रतिनिधित्व करता है, और
* माता-पिता/बच्चे का संबंध सरणी में तत्वों के सूचकांकों द्वारा [[अंतर्निहित डेटा संरचना]] है।
* माता-पिता/बच्चे का संबंध सरणी में तत्वों के सूचकांकों द्वारा [[अंतर्निहित डेटा संरचना]] है।


[[File:Heap-as-array.svg|thumb|upright=1.5|एक पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे एक सरणी में कैसे संग्रहीत किया जाएगा।]]बाइनरी हीप के लिए, सरणी में, पहले इंडेक्स में मूल तत्व होता है। सरणी के अगले दो सूचकांकों में रूट के बच्चे शामिल हैं। अगले चार सूचकांकों में रूट के दो चाइल्ड नोड्स के चार बच्चे शामिल हैं, इत्यादि। इसलिए, सूचकांक पर एक नोड दिया गया है {{mvar|i}}, इसके बच्चे सूचकांकों पर हैं {{tmath|2i + 1}} और {{tmath|2i + 2}}, और इसका पेरेंट इंडेक्स पर है {{math|⌊(''i''−1)/2⌋}}. यह सरल अनुक्रमण योजना पेड़ को ऊपर या नीचे ले जाने को कुशल बनाती है।
[[File:Heap-as-array.svg|thumb|upright=1.5|पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे सरणी में कैसे संग्रहीत किया जाएगा।]]बाइनरी हीप के लिए, सरणी में, पहले इंडेक्स में मूल तत्व होता है। सरणी के अगले दो सूचकांकों में रूट के बच्चे शामिल हैं। अगले चार सूचकांकों में रूट के दो चाइल्ड नोड्स के चार बच्चे शामिल हैं, इत्यादि। इसलिए, सूचकांक पर नोड दिया गया है {{mvar|i}}, इसके बच्चे सूचकांकों पर हैं {{tmath|2i + 1}} और {{tmath|2i + 2}}, और इसका पेरेंट इंडेक्स पर है {{math|⌊(''i''−1)/2⌋}}. यह सरल अनुक्रमण योजना पेड़ को ऊपर या नीचे ले जाने को कुशल बनाती है।


ढेर को संतुलित करना सिफ्ट-अप या सिफ्ट-डाउन ऑपरेशन (अव्यवस्थित तत्वों की अदला-बदली) द्वारा किया जाता है। चूँकि हम अतिरिक्त मेमोरी (उदाहरण के लिए, नोड्स के लिए) की आवश्यकता के बिना किसी सरणी से ढेर बना सकते हैं, हीप्सॉर्ट का उपयोग किसी सरणी को उसी स्थान पर सॉर्ट करने के लिए किया जा सकता है।
ढेर को संतुलित करना सिफ्ट-अप या सिफ्ट-डाउन ऑपरेशन (अव्यवस्थित तत्वों की अदला-बदली) द्वारा किया जाता है। चूँकि हम अतिरिक्त मेमोरी (उदाहरण के लिए, नोड्स के लिए) की आवश्यकता के बिना किसी सरणी से ढेर बना सकते हैं, हीप्सॉर्ट का उपयोग किसी सरणी को उसी स्थान पर सॉर्ट करने के लिए किया जा सकता है।
Line 48: Line 48:
* सम्मिलन: ढेर के अंत में, पहले उपलब्ध खाली स्थान में नया तत्व जोड़ें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति फिर से स्थापित होने तक नए तत्व (''तैरना'' ऑपरेशन) को छान लें।
* सम्मिलन: ढेर के अंत में, पहले उपलब्ध खाली स्थान में नया तत्व जोड़ें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति फिर से स्थापित होने तक नए तत्व (''तैरना'' ऑपरेशन) को छान लें।
* निष्कर्षण: जड़ को हटा दें और ढेर के अंतिम तत्व को जड़ में डालें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति को फिर से स्थापित करने के लिए नए रूट (''सिंक'' ऑपरेशन) को छान लें।
* निष्कर्षण: जड़ को हटा दें और ढेर के अंतिम तत्व को जड़ में डालें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति को फिर से स्थापित करने के लिए नए रूट (''सिंक'' ऑपरेशन) को छान लें।
* प्रतिस्थापन: जड़ को हटा दें और ''नए'' तत्व को जड़ में डालें और छान लें। जब निष्कर्षण के बाद सम्मिलन की तुलना की जाती है, तो यह एक छानने के कदम से बचता है।
* प्रतिस्थापन: जड़ को हटा दें और ''नए'' तत्व को जड़ में डालें और छान लें। जब निष्कर्षण के बाद सम्मिलन की तुलना की जाती है, तो यह छानने के कदम से बचता है।


तत्वों की दी गई सारणी से एक बाइनरी (या ''डी''-एरी) ढेर का निर्माण क्लासिक हीप्सोर्ट#वेरिएशन का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें सबसे खराब स्थिति में तुलना की संख्या 2''एन' के बराबर होती है। ' − 2''''<sub>2</sub>(एन) - ई<sub>2</sub>(एन) (एक बाइनरी ढेर के लिए), जहां एस<sub>2</sub>(एन) एन और ई के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है<sub>2</sub>(एन) एन के अभाज्य गुणनखंडन में 2 का घातांक है।<ref>{{citation
तत्वों की दी गई सारणी से बाइनरी (या ''डी''-एरी) ढेर का निर्माण क्लासिक हीप्सोर्ट#वेरिएशन का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें सबसे खराब स्थिति में तुलना की संख्या 2''एन' के बराबर होती है। ' − 2''''<sub>2</sub>(एन) - ई<sub>2</sub>(एन) (बाइनरी ढेर के लिए), जहां एस<sub>2</sub>(एन) एन और ई के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है<sub>2</sub>(एन) एन के अभाज्य गुणनखंडन में 2 का घातांक है।<ref>{{citation
  | last1 = Suchenek | first1 = Marek A.
  | last1 = Suchenek | first1 = Marek A.
  | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
  | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
Line 92: Line 92:


* हीपसॉर्ट: सर्वोत्तम सॉर्टिंग विधियों में से एक, यथास्थान और बिना किसी द्विघात सबसे खराब स्थिति के।
* हीपसॉर्ट: सर्वोत्तम सॉर्टिंग विधियों में से एक, यथास्थान और बिना किसी द्विघात सबसे खराब स्थिति के।
* चयन एल्गोरिदम: एक ढेर निरंतर समय में न्यूनतम या अधिकतम तत्व तक पहुंच की अनुमति देता है, और अन्य चयन (जैसे कि माध्यिका या केटीएच-तत्व) ढेर में मौजूद डेटा पर उप-रेखीय समय में किया जा सकता है।<ref>{{citation
* चयन एल्गोरिदम: ढेर निरंतर समय में न्यूनतम या अधिकतम तत्व तक पहुंच की अनुमति देता है, और अन्य चयन (जैसे कि माध्यिका या केटीएच-तत्व) ढेर में मौजूद डेटा पर उप-रेखीय समय में किया जा सकता है।<ref>{{citation
  | last = Frederickson
  | last = Frederickson
  | first = Greg N.
  | first = Greg N.
Line 111: Line 111:
  }}</ref>
  }}</ref>
* एल्गोरिदम की सूची#ग्राफ़ एल्गोरिदम: आंतरिक ट्रैवर्सल डेटा संरचनाओं के रूप में हीप्स का उपयोग करके, रन टाइम को बहुपद क्रम से कम किया जाएगा। ऐसी समस्याओं के उदाहरण हैं प्राइम का एल्गोरिदम|प्रिम का न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम और डिज्क्स्ट्रा का एल्गोरिदम|डिज्क्स्ट्रा का सबसे छोटा-पथ एल्गोरिदम।
* एल्गोरिदम की सूची#ग्राफ़ एल्गोरिदम: आंतरिक ट्रैवर्सल डेटा संरचनाओं के रूप में हीप्स का उपयोग करके, रन टाइम को बहुपद क्रम से कम किया जाएगा। ऐसी समस्याओं के उदाहरण हैं प्राइम का एल्गोरिदम|प्रिम का न्यूनतम-स्पैनिंग-ट्री एल्गोरिदम और डिज्क्स्ट्रा का एल्गोरिदम|डिज्क्स्ट्रा का सबसे छोटा-पथ एल्गोरिदम।
*प्राथमिकता कतार: प्राथमिकता कतार एक सूची या मानचित्र की तरह एक अमूर्त अवधारणा है; जिस तरह एक सूची को एक लिंक्ड सूची या सरणी के साथ लागू किया जा सकता है, उसी तरह प्राथमिकता कतार को ढेर या कई अन्य तरीकों से लागू किया जा सकता है।
*प्राथमिकता कतार: प्राथमिकता कतार सूची या मानचित्र की तरह अमूर्त अवधारणा है; जिस तरह सूची को लिंक्ड सूची या सरणी के साथ लागू किया जा सकता है, उसी तरह प्राथमिकता कतार को ढेर या कई अन्य तरीकों से लागू किया जा सकता है।
*[[के-वे मर्ज एल्गोरिदम]]|के-वे मर्ज: एक हीप डेटा संरचना कई पहले से क्रमबद्ध इनपुट स्ट्रीम को एक एकल क्रमबद्ध आउटपुट स्ट्रीम में मर्ज करने के लिए उपयोगी है। विलय की आवश्यकता के उदाहरणों में लॉग संरचित मर्ज ट्री जैसे वितरित डेटा से बाहरी सॉर्टिंग और स्ट्रीमिंग परिणाम शामिल हैं। आंतरिक लूप न्यूनतम तत्व प्राप्त कर रहा है, संबंधित इनपुट स्ट्रीम के लिए अगले तत्व के साथ प्रतिस्थापित कर रहा है, फिर एक सिफ्ट-डाउन हीप ऑपरेशन कर रहा है। (वैकल्पिक रूप से रिप्लेस फ़ंक्शन।) (प्राथमिकता कतार के एक्सट्रैक्ट-मैक्स और इंसर्ट फ़ंक्शंस का उपयोग करना बहुत कम कुशल है।)
*[[के-वे मर्ज एल्गोरिदम]]|के-वे मर्ज: हीप डेटा संरचना कई पहले से क्रमबद्ध इनपुट स्ट्रीम को एकल क्रमबद्ध आउटपुट स्ट्रीम में मर्ज करने के लिए उपयोगी है। विलय की आवश्यकता के उदाहरणों में लॉग संरचित मर्ज ट्री जैसे वितरित डेटा से बाहरी सॉर्टिंग और स्ट्रीमिंग परिणाम शामिल हैं। आंतरिक लूप न्यूनतम तत्व प्राप्त कर रहा है, संबंधित इनपुट स्ट्रीम के लिए अगले तत्व के साथ प्रतिस्थापित कर रहा है, फिर सिफ्ट-डाउन हीप ऑपरेशन कर रहा है। (वैकल्पिक रूप से रिप्लेस फ़ंक्शन।) (प्राथमिकता कतार के एक्सट्रैक्ट-मैक्स और इंसर्ट फ़ंक्शंस का उपयोग करना बहुत कम कुशल है।)
*[[आदेश आँकड़े]]: हीप डेटा संरचना का उपयोग किसी सरणी में सबसे छोटे (या सबसे बड़े) तत्व को कुशलतापूर्वक खोजने के लिए किया जा सकता है।
*[[आदेश आँकड़े]]: हीप डेटा संरचना का उपयोग किसी सरणी में सबसे छोटे (या सबसे बड़े) तत्व को कुशलतापूर्वक खोजने के लिए किया जा सकता है।


==प्रोग्रामिंग भाषा कार्यान्वयन==
==प्रोग्रामिंग भाषा कार्यान्वयन==
* C++ मानक लाइब्रेरी प्रदान करती है {{mono|make_heap}}, {{mono|push_heap}} और {{mono|pop_heap}} हीप्स के लिए एल्गोरिदम (आमतौर पर बाइनरी हीप्स के रूप में लागू किया जाता है), जो मनमाने ढंग से यादृच्छिक एक्सेस [[इटरेटर]] पर काम करते हैं। यह पुनरावृत्तियों को किसी सरणी के संदर्भ के रूप में मानता है, और सरणी-से-ढेर रूपांतरण का उपयोग करता है। यह कंटेनर एडाप्टर भी प्रदान करता है {{mono|priority_queue}}, जो इन सुविधाओं को एक कंटेनर-जैसी कक्षा में लपेटता है। हालाँकि, रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई मानक समर्थन नहीं है।
* C++ मानक लाइब्रेरी प्रदान करती है {{mono|make_heap}}, {{mono|push_heap}} और {{mono|pop_heap}} हीप्स के लिए एल्गोरिदम (आमतौर पर बाइनरी हीप्स के रूप में लागू किया जाता है), जो मनमाने ढंग से यादृच्छिक एक्सेस [[इटरेटर]] पर काम करते हैं। यह पुनरावृत्तियों को किसी सरणी के संदर्भ के रूप में मानता है, और सरणी-से-ढेर रूपांतरण का उपयोग करता है। यह कंटेनर एडाप्टर भी प्रदान करता है {{mono|priority_queue}}, जो इन सुविधाओं को कंटेनर-जैसी कक्षा में लपेटता है। हालाँकि, रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई मानक समर्थन नहीं है।
* बूस्ट ([[सी++]] लाइब्रेरीज़)|बूस्ट सी++ लाइब्रेरीज़ में एक हीप्स लाइब्रेरी शामिल है। एसटीएल के विपरीत, यह कमी और वृद्धि के संचालन का समर्थन करता है, और अतिरिक्त प्रकार के ढेर का समर्थन करता है: विशेष रूप से, यह डी-एरी, द्विपद, फाइबोनैचि, युग्मन और तिरछा ढेर का समर्थन करता है।
* बूस्ट ([[सी++]] लाइब्रेरीज़)|बूस्ट सी++ लाइब्रेरीज़ में हीप्स लाइब्रेरी शामिल है। एसटीएल के विपरीत, यह कमी और वृद्धि के संचालन का समर्थन करता है, और अतिरिक्त प्रकार के ढेर का समर्थन करता है: विशेष रूप से, यह डी-एरी, द्विपद, फाइबोनैचि, युग्मन और तिरछा ढेर का समर्थन करता है।
* D-ary हीप और B-हीप समर्थन के साथ C (प्रोग्रामिंग भाषा) और C++ के लिए [https://github.com/valyala/gheap जेनेरिक हीप कार्यान्वयन] है। यह एसटीएल जैसी एपीआई प्रदान करता है।
* D-ary हीप और B-हीप समर्थन के साथ C (प्रोग्रामिंग भाषा) और C++ के लिए [https://github.com/valyala/gheap जेनेरिक हीप कार्यान्वयन] है। यह एसटीएल जैसी एपीआई प्रदान करता है।
* [[डी (प्रोग्रामिंग भाषा)]] की मानक लाइब्रेरी में [https://dlang.org/phobos/std_container_binaryheap.html शामिल है {{mono|std.container.BinaryHeap}}], जिसे डी के [https://tour.dlang.org/tour/en/basics/ranges श्रेणियों] के संदर्भ में लागू किया गया है। इंस्टेंस का निर्माण किसी भी [https://dlang.org/phobos/std_range_priitives.html#isRandomAccessRange रैंडम-एक्सेस रेंज] से किया जा सकता है। {{mono|BinaryHeap}} एक [https://dlang.org/phobos/std_range_primitives.html#isInputRange इनपुट रेंज इंटरफ़ेस] को उजागर करता है जो डी के अंतर्निहित के साथ पुनरावृत्ति की अनुमति देता है {{mono|foreach}} कथन और रेंज-आधारित एपीआई के साथ एकीकरण [https://dlang.org/phobos/std_algorithm.html {{mono|std.algorithm}} पैकेट]।
* [[डी (प्रोग्रामिंग भाषा)]] की मानक लाइब्रेरी में [https://dlang.org/phobos/std_container_binaryheap.html शामिल है {{mono|std.container.BinaryHeap}}], जिसे डी के [https://tour.dlang.org/tour/en/basics/ranges श्रेणियों] के संदर्भ में लागू किया गया है। इंस्टेंस का निर्माण किसी भी [https://dlang.org/phobos/std_range_priitives.html#isRandomAccessRange रैंडम-एक्सेस रेंज] से किया जा सकता है। {{mono|BinaryHeap}} [https://dlang.org/phobos/std_range_primitives.html#isInputRange इनपुट रेंज इंटरफ़ेस] को उजागर करता है जो डी के अंतर्निहित के साथ पुनरावृत्ति की अनुमति देता है {{mono|foreach}} कथन और रेंज-आधारित एपीआई के साथ एकीकरण [https://dlang.org/phobos/std_algorithm.html {{mono|std.algorithm}} पैकेट]।
* [[हास्केल (प्रोग्रामिंग भाषा)]] के लिए [https://hackage.haskell.org/package/heaps है {{mono|Data.Heap}}] मापांक।
* [[हास्केल (प्रोग्रामिंग भाषा)]] के लिए [https://hackage.haskell.org/package/heaps है {{mono|Data.Heap}}] मापांक।
* [[जावा (प्रोग्रामिंग भाषा)]] प्लेटफ़ॉर्म (संस्करण 1.5 से) क्लास के साथ बाइनरी हीप कार्यान्वयन प्रदान करता है {{Javadoc:SE|package=java.util|java/util|PriorityQueue}} [[जावा संग्रह ढांचा]] में। यह वर्ग डिफ़ॉल्ट रूप से एक न्यूनतम-ढेर लागू करता है; मैक्स-हीप को लागू करने के लिए, प्रोग्रामर को एक कस्टम तुलनित्र लिखना चाहिए। प्रतिस्थापन, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई समर्थन नहीं है।
* [[जावा (प्रोग्रामिंग भाषा)]] प्लेटफ़ॉर्म (संस्करण 1.5 से) क्लास के साथ बाइनरी हीप कार्यान्वयन प्रदान करता है {{Javadoc:SE|package=java.util|java/util|PriorityQueue}} [[जावा संग्रह ढांचा]] में। यह वर्ग डिफ़ॉल्ट रूप से न्यूनतम-ढेर लागू करता है; मैक्स-हीप को लागू करने के लिए, प्रोग्रामर को कस्टम तुलनित्र लिखना चाहिए। प्रतिस्थापन, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई समर्थन नहीं है।
* [[पायथन (प्रोग्रामिंग भाषा)]] में एक [https://docs.python.org/library/heapq.html है {{mono|heapq}}] मॉड्यूल जो बाइनरी हीप का उपयोग करके प्राथमिकता कतार लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए एक हीप्रप्लेस फ़ंक्शन को उजागर करती है।
* [[पायथन (प्रोग्रामिंग भाषा)]] में [https://docs.python.org/library/heapq.html है {{mono|heapq}}] मॉड्यूल जो बाइनरी हीप का उपयोग करके प्राथमिकता कतार लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए हीप्रप्लेस फ़ंक्शन को उजागर करती है।
* [[PHP]] में अधिकतम-ढेर दोनों हैं ({{mono|SplMaxHeap}}) और न्यूनतम-ढेर ({{mono|SplMinHeap}}) मानक PHP लाइब्रेरी में संस्करण 5.3 के अनुसार।
* [[PHP]] में अधिकतम-ढेर दोनों हैं ({{mono|SplMaxHeap}}) और न्यूनतम-ढेर ({{mono|SplMinHeap}}) मानक PHP लाइब्रेरी में संस्करण 5.3 के अनुसार।
* [[पर्ल]] ने [https://metacpan.org/module/Heap में बाइनरी, बाइनोमियल और फाइबोनैचि हीप्स का कार्यान्वयन किया है {{mono|Heap}}] वितरण [[सीपीएएन]] पर उपलब्ध है।
* [[पर्ल]] ने [https://metacpan.org/module/Heap में बाइनरी, बाइनोमियल और फाइबोनैचि हीप्स का कार्यान्वयन किया है {{mono|Heap}}] वितरण [[सीपीएएन]] पर उपलब्ध है।
* गो (प्रोग्रामिंग भाषा) भाषा में एक [http://golang.org/pkg/container/heap/ शामिल है {{mono|heap}}] हीप एल्गोरिदम वाला पैकेज जो एक मनमाने प्रकार पर काम करता है जो किसी दिए गए इंटरफ़ेस को संतुष्ट करता है। वह पैकेज रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन का समर्थन नहीं करता है।
* गो (प्रोग्रामिंग भाषा) भाषा में [http://golang.org/pkg/container/heap/ शामिल है {{mono|heap}}] हीप एल्गोरिदम वाला पैकेज जो मनमाने प्रकार पर काम करता है जो किसी दिए गए इंटरफ़ेस को संतुष्ट करता है। वह पैकेज रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन का समर्थन नहीं करता है।
* Apple की [[कोर फाउंडेशन]] लाइब्रेरी में एक [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html शामिल है {{mono|CFBinaryHeap}}] संरचना।
* Apple की [[कोर फाउंडेशन]] लाइब्रेरी में [https://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html शामिल है {{mono|CFBinaryHeap}}] संरचना।
* [[फिरौन]] के पास परीक्षण मामलों के एक सेट के साथ संग्रह-अनुक्रमणीय पैकेज में ढेर का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में एक ढेर का उपयोग किया जाता है।
* [[फिरौन]] के पास परीक्षण मामलों के सेट के साथ संग्रह-अनुक्रमणीय पैकेज में ढेर का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में ढेर का उपयोग किया जाता है।
* रस्ट (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा में बाइनरी मैक्स-हीप कार्यान्वयन है, [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html {{mono|BinaryHeap}}], में {{mono|collections}} इसके मानक पुस्तकालय का मॉड्यूल।
* रस्ट (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा में बाइनरी मैक्स-हीप कार्यान्वयन है, [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html {{mono|BinaryHeap}}], में {{mono|collections}} इसके मानक पुस्तकालय का मॉड्यूल।
* .NET में [https://docs.microsoft.com/dotnet/api/system.collections.generic.priorityqueue-2 प्राथमिकता क्यू] वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।
* .NET में [https://docs.microsoft.com/dotnet/api/system.collections.generic.priorityqueue-2 प्राथमिकता क्यू] वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।
Line 137: Line 137:
* [[कतार (सार डेटा प्रकार)]]
* [[कतार (सार डेटा प्रकार)]]
* वृक्ष (डेटा संरचना)
* वृक्ष (डेटा संरचना)
* ट्रैप, ढेर-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का एक रूप
* ट्रैप, ढेर-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का रूप


==संदर्भ==
==संदर्भ==

Revision as of 15:11, 23 July 2023

For मेमोरी हीप (निम्न-स्तरीय कंप्यूटर प्रोग्रामिंग में), जिसका डेटा संरचना से कोई संबंध नहीं है, see C डायनामिक मेमोरी आवंटन.
एक बाइनरी वृक्ष मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं

कंप्यूटर विज्ञान में, हीप विशेष [[वृक्ष (डेटा संरचना)]]-आधारित डेटा संरचना है जो हीप संपत्ति को संतुष्ट करती है: अधिकतम हीप में, किसी दिए गए नोड (कंप्यूटर विज्ञान) सी के लिए, यदि पी मूल नोड है C, तो P की कुंजी ('मान) C की कुंजी से अधिक या उसके बराबर है। न्यूनतम ढेर में, P की कुंजी, C की कुंजी से कम या उसके बराबर है सी की कुंजी[1] ढेर के शीर्ष पर स्थित नोड (बिना माता-पिता के) को रूट नोड कहा जाता है।

हीप अमूर्त डेटा प्रकार का अधिकतम कुशल कार्यान्वयन है जिसे प्राथमिकता कतार कहा जाता है, और वास्तव में, प्राथमिकता कतारों को अक्सर ढेर के रूप में संदर्भित किया जाता है, तथापि उन्हें कैसे भी लागू किया जा सकता है। ढेर में, उच्चतम (या निम्नतम) प्राथमिकता वाला तत्व हमेशा जड़ में संग्रहीत होता है। हालाँकि, ढेर क्रमबद्ध संरचना नहीं है; इसे आंशिक रूप से ऑर्डर किया गया माना जा सकता है। ढेर उपयोगी डेटा संरचना है जब उच्चतम (या निम्नतम) प्राथमिकता के साथ ऑब्जेक्ट को बार-बार हटाना आवश्यक होता है, या जब सम्मिलन को रूट नोड के निष्कासन के साथ जोड़ने की आवश्यकता होती है।

ढेर का सामान्य कार्यान्वयन बाइनरी ढेर है, जिसमें पेड़ बाइनरी_ट्री#Types_of_binary_trees है[2] बाइनरी ट्री (चित्र देखें)। हीप डेटा संरचना, विशेष रूप से बाइनरी हीप, 1964 में जेडब्ल्यूजे विलियम्स द्वारा ढेर बनाएं और छांटें सॉर्टिंग एल्गोरिदम के लिए डेटा संरचना के रूप में पेश की गई थी।[3] दिज्क्स्ट्रा के एल्गोरिदम जैसे कई कुशल ग्राफ एल्गोरिदम में भी हीप्स महत्वपूर्ण हैं। जब ढेर पूर्ण बाइनरी ट्री होता है, तो इसकी ऊंचाई सबसे छोटी होती है - एन नोड्स वाले ढेर और प्रत्येक नोड के लिए शाखाओं में हमेशा लॉग होता हैa एन ऊंचाई.

ध्यान दें, जैसा कि ग्राफ़िक में दिखाया गया है, भाई-बहनों या चचेरे भाइयों के बीच कोई निहित आदेश नहीं है और इनऑर्डर ट्रैवर्सल के लिए कोई निहित अनुक्रम नहीं है (जैसा कि, उदाहरण के लिए, बाइनरी सर्च ट्री में होगा)। ऊपर उल्लिखित ढेर संबंध केवल नोड्स और उनके माता-पिता, दादा-दादी आदि के बीच लागू होता है। प्रत्येक नोड में बच्चों की अधिकतम संख्या ढेर के प्रकार पर निर्भर करती है।

संचालन

ढेर से जुड़े सामान्य ऑपरेशन हैं:

बुनियादी
  • फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ पीक (डेटा प्रकार ऑपरेशन))
  • सम्मिलित करें: ढेर में नई कुंजी जोड़ना (उर्फ, पुश)।[4])
  • एक्स्ट्रैक्ट-मैक्स (या एक्स्ट्रैक्ट-मिन): इसे हीप (उर्फ पॉप) से हटाने के बाद अधिकतम हीप [या मिन हीप से न्यूनतम मान] से अधिकतम मूल्य का नोड लौटाता है[5])
  • डिलीट-मैक्स (या डिलीट-मिन): क्रमशः अधिकतम हीप (या मिन हीप) के रूट नोड को हटाना
  • बदलें: रूट पॉप करें और नई कुंजी दबाएं। पॉप के बाद पुश की तुलना में अधिक कुशल, क्योंकि केवल बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के ढेर के लिए उपयुक्त।[6]
निर्माण
  • क्रिएट-हीप: खाली ढेर बनाएं
  • ढेर बनाना: तत्वों की दी गई श्रृंखला से ढेर बनाएं
  • विलय (संघ): दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, मूल ढेर को संरक्षित करना।
  • मेल्ड: दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, जिससे मूल ढेर नष्ट हो जाए।
निरीक्षण
  • आकार: ढेर में वस्तुओं की संख्या लौटाएँ।
  • खाली है: यदि ढेर खाली है तो सही लौटाएं, अन्यथा गलत लौटाएं।
आंतरिक
  • वृद्धि-कुंजी या कमी-कुंजी: कुंजी को क्रमशः अधिकतम या न्यूनतम-ढेर के भीतर अद्यतन करना
  • हटाएं: मनमाना नोड हटाएं (इसके बाद अंतिम नोड को स्थानांतरित करें और ढेर बनाए रखने के लिए छान लें)
  • सिफ्ट-अप: जब तक आवश्यक हो, पेड़ में नोड को ऊपर ले जाएं; सम्मिलन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है। इसे सिफ्ट कहा जाता है क्योंकि नोड पेड़ के ऊपर तब तक चलता रहता है जब तक कि यह सही स्तर तक नहीं पहुंच जाता, जैसे कि छलनी में।
  • सिफ्ट-डाउन: सिफ्ट-अप के समान, पेड़ में नोड को नीचे ले जाएं; हटाने या प्रतिस्थापन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है।

कार्यान्वयन

हीप्स को आमतौर पर सरणी डेटा संरचना के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:

  • सरणी में प्रत्येक तत्व ढेर के नोड का प्रतिनिधित्व करता है, और
  • माता-पिता/बच्चे का संबंध सरणी में तत्वों के सूचकांकों द्वारा अंतर्निहित डेटा संरचना है।
पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे सरणी में कैसे संग्रहीत किया जाएगा।

बाइनरी हीप के लिए, सरणी में, पहले इंडेक्स में मूल तत्व होता है। सरणी के अगले दो सूचकांकों मे