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

Latest revision as of 12:11, 28 July 2023

एक बाइनरी ट्री मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 और 100 के बीच पूर्णांक हैं

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

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

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

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

संचालन

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

मूलभूत

फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ पीक (डेटा प्रकार ऑपरेशन))
सम्मिलित करें: हीप में नई कुंजी जोड़ना (उर्फ, पुश)।^[4])
एक्स्ट्रैक्ट-मैक्स (या एक्स्ट्रैक्ट-मिन): इसे हीप (उर्फ पॉप) से हटाने के बाद अधिकतम हीप [या मिन हीप से न्यूनतम मान] से अधिकतम मूल्य का नोड लौटाता है^[5])
डिलीट-मैक्स (या डिलीट-मिन): क्रमशः अधिकतम हीप (या मिन हीप) के रूट नोड को हटाना
बदलें: रूट पॉप करें और नई कुंजी दबाएं। पॉप के बाद पुश की तुलना में अधिक कुशल, क्योंकि केवल बार संतुलन की आवश्यकता होती है, दो बार नहीं, और निश्चित आकार के हीप के लिए उपयुक्त है।^[6]

निर्माण

क्रिएट-हीप: खाली हीप बनाएं
हीप बनाना: तत्वों की दी गई श्रृंखला से हीप बनाएं
मर्ज (संघ): दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, मूल हीप को संरक्षित करना।
मेल्ड: दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, जिससे मूल हीप नष्ट हो जाए।

निरीक्षण

आकार: हीप में वस्तुओं की संख्या लौटाएँ।
खाली है: यदि हीप खाली है तो सही लौटाएं, अन्यथा गलत लौटाएं।

आंतरिक

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

कार्यान्वयन

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

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

पूर्ण बाइनरी मैक्स-हीप का उदाहरण जिसमें नोड कुंजियाँ 1 से 100 तक पूर्णांक हैं और इसे सरणी में कैसे संग्रहीत किया जाएगा।

बाइनरी हीप के लिए, सरणी में, पहले इंडेक्स में मूल तत्व होता है। सरणी के अगले दो सूचकांकों में रूट के बच्चे सम्मिलित हैं। अगले चार सूचकांकों में रूट के दो चाइल्ड नोड्स के चार बच्चे सम्मिलित हैं, इत्यादि। इसलिए, सूचकांक $i$ पर नोड दिया गया है, इसके बच्चे सूचकांकों $2i+1$ और $2i+2$ पर हैं, और इसका पेरेंट इंडेक् $⌊(i -1)/2⌋$ पर है। यह सरल अनुक्रमण योजना ट्री को ऊपर या नीचे ले जाने को कुशल बनाती है।

हीप को संतुलित करना सिफ्ट-अप या सिफ्ट-डाउन ऑपरेशन (अव्यवस्थित तत्वों की अदला-बदली) द्वारा किया जाता है। चूँकि हम अतिरिक्त मेमोरी (उदाहरण के लिए, नोड्स के लिए) की आवश्यकता के बिना किसी सरणी से हीप बना सकते हैं, हीप्सॉर्ट का उपयोग किसी सरणी को उसी स्थान पर सॉर्ट करने के लिए किया जा सकता है।

किसी तत्व को हीप में डालने या हटाने के बाद, हीप की गुण का उल्लंघन हो सकता है, और सरणी के अन्दर तत्वों को स्वैप करके हीप को फिर से संतुलित किया जाना चाहिए।

चूँकि विभिन्न प्रकार के हीप परिचालन को अलग-अलग तरीके से लागू करते हैं, सबसे आम तरीका इस प्रकार है:

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

तत्वों की दी गई सारणी से एक बाइनरी (या डी-एरी) हीप का निर्माण क्लासिक फ़्लॉइड एल्गोरिदम का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें तुलना की सबसे खराब स्थिति संख्या 2N − 2s₂(N) − e₂(N) (एक बाइनरी हीप के लिए) के बराबर है, जहां s₂(N) N के बाइनरी प्रतिनिधित्व के सभी अंकों का योग है और e₂(N) N के अभाज्य गुणनखंड में 2 का घातांक है।^[7] यह मूल रूप से खाली हीप में लगातार सम्मिलन के अनुक्रम से तेज़ है, जो लॉग-लीनियर है।^{[lower-alpha 1]}

वेरिएंट

विकल्पों के लिए सैद्धांतिक सीमाओं की तुलना

Here are time complexities^[8] of various heap data structures. Function names assume a max-heap. For the meaning of "O(f)" and "Θ(f)" see Big O notation.

Operation	find-max	delete-max	insert	increase-key	meld
Binary^[8]	Θ(1)	Θ(log n)	O(log n)	O(log n)	Θ(n)
Leftist	Θ(1)	Θ(log n)	Θ(log n)	O(log n)	Θ(log n)
Binomial^[8]^[9]	Θ(1)	Θ(log n)	Θ(1)^{[lower-alpha 2]}	Θ(log n)	O(log n)^{[lower-alpha 3]}
Fibonacci^[8]^[10]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	Θ(1)^{[lower-alpha 2]}	Θ(1)
Pairing^[11]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	o(log n)^{[lower-alpha 2]}^{[lower-alpha 4]}	Θ(1)
Brodal^[14]^{[lower-alpha 5]}	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
Rank-pairing^[16]	Θ(1)	O(log n)^{[lower-alpha 2]}	Θ(1)	Θ(1)^{[lower-alpha 2]}	Θ(1)
Strict Fibonacci^[17]	Θ(1)	O(log n)	Θ(1)	Θ(1)	Θ(1)
2–3 heap^[18]	O(log n)	O(log n)^{[lower-alpha 2]}	O(log n)^{[lower-alpha 2]}	Θ(1)	?

↑ Each insertion takes O(log(k)) in the existing size of the heap, thus $\sum _{k=1}^{n}O(\log k)$ . Since $\log n/2=(\log n)-1$ , a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume $k=n$ ; formally the time is $nO(\log n)-O(n)=O(n\log n)$ . This can also be readily seen from Stirling's approximation.
↑ ^2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Amortized time.
↑ n is the size of the larger heap.
↑ Lower bound of $\Omega (\log \log n),$ ^[12] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[13]
↑ Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[15]

अनुप्रयोग

हीप डेटा संरचना में कई अनुप्रयोग हैं।

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

प्रोग्रामिंग भाषा कार्यान्वयन

C++ मानक लाइब्रेरी हीप्स के लिए make_heap, push_heap और pop_heap एल्गोरिदम (सामान्यतः पर बाइनरी हीप्स के रूप में लागू किया जाता है) प्रदान करती है, जो स्वैच्छिक रूप से यादृच्छिक एक्सेस इटरेटर पर काम करते हैं। यह पुनरावृत्तियों को किसी सरणी के संदर्भ के रूप में मानता है, और सरणी-से-हीप रूपांतरण का उपयोग करता है। यह कंटेनर एडाप्टर priority_queue भी प्रदान करता है, जो इन सुविधाओं को कंटेनर-जैसी कक्षा में लपेटता है। चूँकि, रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई मानक समर्थन नहीं है।
बूस्ट सी++ लाइब्रेरीज़ में हीप्स लाइब्रेरी सम्मिलित है। एसटीएल के विपरीत, यह कमी और वृद्धि के संचालन का समर्थन करता है, और अतिरिक्त प्रकार के हीप का समर्थन करता है: विशेष रूप से, यह डी-एरी, द्विपद, फाइबोनैचि, युग्मन और स्कू हीप का समर्थन करता है।
डी-एरी हीप और बी-हीप समर्थन के साथ C (प्रोग्रामिंग भाषा) और C++ के लिए जेनेरिक हीप कार्यान्वयन है। यह एसटीएल जैसी एपीआई प्रदान करता है।
डी (प्रोग्रामिंग भाषा) की मानक लाइब्रेरी में std.container.BinaryHeap सम्मिलित है, जिसे डी के श्रेणियों के संदर्भ में लागू किया गया है। इंस्टेंस का निर्माण किसी भी रैंडम-एक्सेस रेंज से किया जा सकता है। BinaryHeap एक इनपुट रेंज इंटरफ़ेस को प्रकाशित करता है जो डी के अंतर्निहित foreach स्टेटमेंट के साथ पुनरावृत्ति और std.algorithm पैकेट के रेंज-आधारित एपीआई के साथ एकीकरण की अनुमति देता है।
हास्केल (प्रोग्रामिंग भाषा) के लिए Data.Heap मापांक है।
जावा (प्रोग्रामिंग भाषा) प्लेटफ़ॉर्म (संस्करण 1.5 से) जावा कलेक्शन फ्रेमवर्क में क्लास java.util.PriorityQueue के साथ एक बाइनरी हीप कार्यान्वयन प्रदान करता है। यह वर्ग डिफ़ॉल्ट रूप से न्यूनतम-हीप लागू करता है; मैक्स-हीप को लागू करने के लिए, प्रोग्रामर को कस्टम तुलनित्र लिखना चाहिए। प्रतिस्थापन, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन के लिए कोई समर्थन नहीं है।
पायथन (प्रोग्रामिंग भाषा) में एक heapq मॉड्यूल है जो बाइनरी हीप का उपयोग करके प्राथमिकता क्रम लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए हीप्रप्लेस फ़ंक्शन को प्रकाशित करती है।
मानक पीएचपी लाइब्रेरी में संस्करण 5.3 के अनुसार पीएचपी में मैक्स-हीप (SplMaxHeap) और न्यूनतम-हीप (SplMinHeap) दोनों हैं।
पर्ल के पास सीपीएएन पर उपलब्ध हीप वितरण में बाइनरी, बाइनोमियल और फाइबोनैचि हीप्स Heap का कार्यान्वयन किया हैं।
गो (प्रोग्रामिंग भाषा) भाषा में heap सम्मिलित है हीप एल्गोरिदम वाला पैकेज जो स्वैच्छिक प्रकार पर काम करता है जो किसी दिए गए इंटरफ़ेस को संतुष्ट करता है। वह पैकेज रिप्लेस, सिफ्ट-अप/सिफ्ट-डाउन, या कमी/वृद्धि-कुंजी संचालन का समर्थन नहीं करता है।
Apple की कोर फाउंडेशन लाइब्रेरी में CFBinaryHeap संरचना सम्मिलित है।
फिरौन के पास परीक्षण मामलों के सेट के साथ संग्रह-अनुक्रमणीय पैकेज में हीप का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में हीप का उपयोग किया जाता है।
रस्ट प्रोग्रामिंग भाषा में इसके मानक लाइब्रेरी के collections मॉड्यूल में एक बाइनरी मैक्स-हीप कार्यान्वयन, BinaryHeap है।
.NET में प्राथमिकता क्यू वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।

यह भी देखें

छँटाई एल्गोरिथ्म
डेटा संरचना खोजें
स्टैक (सार डेटा प्रकार)
क्रम (सार डेटा प्रकार)
ट्री (डेटा संरचना)
ट्रैप, हीप-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का रूप

संदर्भ

↑ 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.
↑ CORMEN, THOMAS H. (2009). एल्गोरिदम का परिचय. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.
↑ Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop
↑ The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace
↑ Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.
↑ ^8.0 ^8.1 ^8.2 ^8.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.
↑ "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.
↑ Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.
↑ Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2
↑ Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.
↑ Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.
↑ Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58
↑ Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.
↑ Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.
↑ Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.
↑ Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12
↑ Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), vol. 104, Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030, archived from the original (PDF) on 2012-12-03, retrieved 2010-10-31

बाहरी संबंध

Heap at Wolfram MathWorld
Explanation of how the basic heap algorithms work
Bentley, Jon Louis (2000). Programming Pearls (2nd ed.). Addison Wesley. pp. 147–162. ISBN 0201657880.

[8] Each insertion takes O(log(k)) in the existing size of the heap, thus $\sum _{k=1}^{n}O(\log k)$ . Since $\log n/2=(\log n)-1$ , a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume $k=n$ ; formally the time is $nO(\log n)-O(n)=O(n\log n)$ . This can also be readily seen from Stirling's approximation.

[amortized-11] 2.0 ^2.1 ^2.2 ^2.3 ^2.4 ^2.5 ^2.6 ^2.7 ^2.8 Amortized time.

[meld-12] s the size of the larger heap.

[pairingdecreasekey-17] Lower bound of $\Omega (\log \log n),$ ^[12] upper bound of $O(2^{2{\sqrt {\log \log n}}}).$ ^[13]

[brodal-20] Brodal and Okasaki later describe a persistent variant with the same bounds except for decrease-key, which is not supported. Heaps with n elements can be constructed bottom-up in O(n).^[15]

[1] 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.

[2] CORMEN, THOMAS H. (2009). एल्गोरिदम का परिचय. United States of America: The MIT Press Cambridge, Massachusetts London, England. pp. 151–152. ISBN 978-0-262-03384-8.

[3] Williams, J. W. J. (1964), "Algorithm 232 - Heapsort", Communications of the ACM, 7 (6): 347–348, doi:10.1145/512274.512284

[4] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappush

[5] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heappop

[6] The Python Standard Library, 8.4. heapq — Heap queue algorithm, heapq.heapreplace

[7] Suchenek, Marek A. (2012), "Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program", Fundamenta Informaticae, IOS Press, 120 (1): 75–92, doi:10.3233/FI-2012-751.

[CLRS-9] 8.0 ^8.1 ^8.2 ^8.3 Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L. (1990). Introduction to Algorithms (1st ed.). MIT Press and McGraw-Hill. ISBN 0-262-03141-8.

[10] "Binomial Heap | Brilliant Math & Science Wiki". brilliant.org (in English). Retrieved 2019-09-30.

[Fredman_And_Tarjan-13] Fredman, Michael Lawrence; Tarjan, Robert E. (July 1987). "Fibonacci heaps and their uses in improved network optimization algorithms" (PDF). Journal of the Association for Computing Machinery. 34 (3): 596–615. CiteSeerX 10.1.1.309.8927. doi:10.1145/28869.28874.

[Iacono-14] Iacono, John (2000), "Improved upper bounds for pairing heaps", Proc. 7th Scandinavian Workshop on Algorithm Theory (PDF), Lecture Notes in Computer Science, vol. 1851, Springer-Verlag, pp. 63–77, arXiv:1110.4428, CiteSeerX 10.1.1.748.7812, doi:10.1007/3-540-44985-X_5, ISBN 3-540-67690-2

[Fredman1999-15] Fredman, Michael Lawrence (July 1999). "On the Efficiency of Pairing Heaps and Related Data Structures" (PDF). Journal of the Association for Computing Machinery. 46 (4): 473–501. doi:10.1145/320211.320214.

[16] Pettie, Seth (2005). Towards a Final Analysis of Pairing Heaps (PDF). FOCS '05 Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science. pp. 174–183. CiteSeerX 10.1.1.549.471. doi:10.1109/SFCS.2005.75. ISBN 0-7695-2468-0.

[18] Brodal, Gerth S. (1996), "Worst-Case Efficient Priority Queues" (PDF), Proc. 7th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 52–58

[19] Goodrich, Michael T.; Tamassia, Roberto (2004). "7.3.6. Bottom-Up Heap Construction". Data Structures and Algorithms in Java (3rd ed.). pp. 338–341. ISBN 0-471-46983-1.

[21] Haeupler, Bernhard; Sen, Siddhartha; Tarjan, Robert E. (November 2011). "Rank-pairing heaps" (PDF). SIAM J. Computing. 40 (6): 1463–1485. doi:10.1137/100785351.

[22] Brodal, Gerth Stølting; Lagogiannis, George; Tarjan, Robert E. (2012). Strict Fibonacci heaps (PDF). Proceedings of the 44th symposium on Theory of Computing - STOC '12. pp. 1177–1184. CiteSeerX 10.1.1.233.1740. doi:10.1145/2213977.2214082. ISBN 978-1-4503-1245-5.

[23] Takaoka, Tadao (1999), Theory of 2–3 Heaps (PDF), p. 12

[24] Frederickson, Greg N. (1993), "An Optimal Algorithm for Selection in a Min-Heap", Information and Computation (PDF), vol. 104, Academic Press, pp. 197–214, doi:10.1006/inco.1993.1030, archived from the original (PDF) on 2012-12-03, retrieved 2010-10-31

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[lower-alpha 1]

[8]

[9]

[lower-alpha 2]

[lower-alpha 3]

[10]

[11]

[lower-alpha 4]

[14]

[lower-alpha 5]

[16]

[17]

[18]

[12]

[13]

[15]

[19]

@@ Line 1: / Line 1: @@
 {{short description|Computer science data structure}}
 {{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 की कुंजी से अधिक या उसके समान है। एक मिनट के हीप में, 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> एन ऊंचाई.
+हीप का सामान्य कार्यान्वयन [[ बाइनरी ढेर |बाइनरी हीप]] है, जिसमें ट्री लगभग पूर्ण<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> दिज्क्स्ट्रा के एल्गोरिदम जैसे कई कुशल [[ग्राफ एल्गोरिदम]] में भी हीप्स महत्वपूर्ण हैं। जब हीप पूर्ण बाइनरी ट्री होता है, तो इसकी ऊंचाई सबसे छोटी होती है - ''N'' नोड्स वाले हीप और प्रत्येक नोड के लिए शाखाओं में सदैव ''log<sub>a</sub> N'' ऊंचाई होती है।
-ध्यान दें, जैसा कि ग्राफ़िक में दिखाया गया है, भाई-बहनों या चचेरे भाइयों के बीच कोई निहित आदेश नहीं है और [[इनऑर्डर ट्रैवर्सल]] के लिए कोई निहित अनुक्रम नहीं है (जैसा कि, उदाहरण के लिए, [[बाइनरी सर्च ट्री]] में होगा)। ऊपर उल्लिखित ढेर संबंध केवल नोड्स और उनके माता-पिता, दादा-दादी आदि के बीच लागू होता है। प्रत्येक नोड में बच्चों की अधिकतम संख्या ढेर के प्रकार पर निर्भर करती है।
+ध्यान दें, जैसा कि ग्राफ़िक में दिखाया गया है, सिब्लिंग्स या कजिन के बीच कोई निहित आदेश नहीं है और [[इनऑर्डर ट्रैवर्सल|इन-ऑर्डर ट्रैवर्सल]] के लिए कोई निहित अनुक्रम (जैसा कि, उदाहरण के लिए, [[बाइनरी सर्च ट्री]] में होगा) नहीं है। ऊपर उल्लिखित हीप संबंध केवल नोड्स और उनके पैरेंट्स, ग्रैंडपैरेंट्स आदि के बीच लागू होता है। प्रत्येक नोड में बच्चों की अधिकतम संख्या हीप के प्रकार पर निर्भर करती है।
 ==संचालन==
-ढेर से जुड़े सामान्य ऑपरेशन हैं:
+हीप से जुड़े सामान्य ऑपरेशन हैं:
-;बुनियादी
+;मूलभूत
 * फाइंड-मैक्स (या फाइंड-मिन): क्रमशः अधिकतम-हीप का अधिकतम आइटम, या मिन-हीप का न्यूनतम आइटम ढूंढें (उर्फ [[पीक (डेटा प्रकार ऑपरेशन)]])
-* सम्मिलित करें: ढेर में नई कुंजी जोड़ना (उर्फ, पुश)।<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.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>
 ;निर्माण
-* क्रिएट-हीप: खाली ढेर बनाएं
+* क्रिएट-हीप: खाली हीप बनाएं
-* ढेर बनाना: तत्वों की दी गई श्रृंखला से ढेर बनाएं
+* हीप बनाना: तत्वों की दी गई श्रृंखला से हीप बनाएं
-* विलय (संघ): दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, मूल ढेर को संरक्षित करना।
+* मर्ज (संघ): दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, मूल हीप को संरक्षित करना।
-* मेल्ड: दो ढेरों को जोड़कर वैध नया ढेर बनाना जिसमें दोनों के सभी तत्व शामिल हों, जिससे मूल ढेर नष्ट हो जाए।
+* मेल्ड: दो हीप्स को जोड़कर वैध नया हीप बनाना जिसमें दोनों के सभी तत्व सम्मिलित हों, जिससे मूल हीप नष्ट हो जाए।
 ;निरीक्षण
-* आकार: ढेर में वस्तुओं की संख्या लौटाएँ।
+* आकार: हीप में वस्तुओं की संख्या लौटाएँ।
-* खाली है: यदि ढेर खाली है तो सही लौटाएं, अन्यथा गलत लौटाएं।
+* खाली है: यदि हीप खाली है तो सही लौटाएं, अन्यथा गलत लौटाएं।
 ;आंतरिक
-* वृद्धि-कुंजी या कमी-कुंजी: कुंजी को क्रमशः अधिकतम या न्यूनतम-ढेर के भीतर अद्यतन करना
+* इनक्रीस-कुंजी या डिकक्रीस-कुंजी: कुंजी को क्रमशः अधिकतम या न्यूनतम-हीप के अन्दर अद्यतन करना
-* हटाएं: मनमाना नोड हटाएं (इसके बाद अंतिम नोड को स्थानांतरित करें और ढेर बनाए रखने के लिए छान लें)
+* हटाएं: मनमाना नोड (इसके बाद हीप को बनाए रखने के लिए अंतिम नोड को गतिमान और शिफ्ट करना होता है) हटाएं
-* सिफ्ट-अप: जब तक आवश्यक हो, पेड़ में नोड को ऊपर ले जाएं; सम्मिलन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है। इसे सिफ्ट कहा जाता है क्योंकि नोड पेड़ के ऊपर तब तक चलता रहता है जब तक कि यह सही स्तर तक नहीं पहुंच जाता, जैसे कि छलनी में।
+* सिफ्ट-अप: जब तक आवश्यक हो, ट्री में नोड को ऊपर ले जाएं; सम्मिलन के बाद हीप की स्थिति को रिज्यूमेड करने के लिए उपयोग किया जाता है। इसे सिफ्ट कहा जाता है क्योंकि नोड ट्री के ऊपर तब तक चलता रहता है जब तक कि यह सही स्तर तक नहीं पहुंच जाता, जैसे कि सीव में।
-* सिफ्ट-डाउन: सिफ्ट-अप के समान, पेड़ में नोड को नीचे ले जाएं; हटाने या प्रतिस्थापन के बाद ढेर की स्थिति को बहाल करने के लिए उपयोग किया जाता है।
+* सिफ्ट-डाउन: सिफ्ट-अप के समान, ट्री में नोड को नीचे ले जाएं; हटाने या प्रतिस्थापन के बाद हीप की स्थिति को रिज्यूमेड करने के लिए उपयोग किया जाता है।
 ==कार्यान्वयन==
-हीप्स को आमतौर पर [[सरणी डेटा संरचना]] के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:
+हीप्स को सामान्यतः पर [[सरणी डेटा संरचना]] के साथ कार्यान्वित किया जाता है, जो इस प्रकार है:
-* सरणी में प्रत्येक तत्व ढेर के नोड का प्रतिनिधित्व करता है, और
+* सरणी में प्रत्येक तत्व हीप के नोड का प्रतिनिधित्व करता है, और
-* माता-पिता/बच्चे का संबंध सरणी में तत्वों के सूचकांकों द्वारा [[अंतर्निहित डेटा संरचना]] है।
+* पैरेंट्स/चाइल्ड का संबंध सरणी में तत्वों के सूचकांकों द्वारा [[अंतर्निहित डेटा संरचना]] है।
-[[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⌋}} पर है। यह सरल अनुक्रमण योजना ट्री को ऊपर या नीचे ले जाने को कुशल बनाती है।
-ढेर को संतुलित करना सिफ्ट-अप या सिफ्ट-डाउन ऑपरेशन (अव्यवस्थित तत्वों की अदला-बदली) द्वारा किया जाता है। चूँकि हम अतिरिक्त मेमोरी (उदाहरण के लिए, नोड्स के लिए) की आवश्यकता के बिना किसी सरणी से ढेर बना सकते हैं, हीप्सॉर्ट का उपयोग किसी सरणी को उसी स्थान पर सॉर्ट करने के लिए किया जा सकता है।
+हीप को संतुलित करना सिफ्ट-अप या सिफ्ट-डाउन ऑपरेशन (अव्यवस्थित तत्वों की अदला-बदली) द्वारा किया जाता है। चूँकि हम अतिरिक्त मेमोरी (उदाहरण के लिए, नोड्स के लिए) की आवश्यकता के बिना किसी सरणी से हीप बना सकते हैं, हीप्सॉर्ट का उपयोग किसी सरणी को उसी स्थान पर सॉर्ट करने के लिए किया जा सकता है।
-किसी तत्व को ढेर में डालने या हटाने के बाद, ढेर की संपत्ति का उल्लंघन हो सकता है, और सरणी के भीतर तत्वों को स्वैप करके ढेर को फिर से संतुलित किया जाना चाहिए।
+किसी तत्व को हीप में डालने या हटाने के बाद, हीप की गुण का उल्लंघन हो सकता है, और सरणी के अन्दर तत्वों को स्वैप करके हीप को फिर से संतुलित किया जाना चाहिए।
-हालाँकि विभिन्न प्रकार के ढेर परिचालन को अलग-अलग तरीके से लागू करते हैं, सबसे आम तरीका इस प्रकार है:
+चूँकि विभिन्न प्रकार के हीप परिचालन को अलग-अलग तरीके से लागू करते हैं, सबसे आम तरीका इस प्रकार है:
-* सम्मिलन: ढेर के अंत में, पहले उपलब्ध खाली स्थान में नया तत्व जोड़ें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति फिर से स्थापित होने तक नए तत्व (''तैरना'' ऑपरेशन) को छान लें।
+* '''इंसर्शन''': हीप के अंत में, पहले उपलब्ध खाली स्थान में नया तत्व जोड़ें। यदि यह हीप गुण का उल्लंघन करेगा, तो हीप गुण फिर से स्थापित होने तक नए तत्व (''तैरना'' ऑपरेशन) को शिफ्ट डाउन करे।
-* निष्कर्षण: जड़ को हटा दें और ढेर के अंतिम तत्व को जड़ में डालें। यदि यह ढेर संपत्ति का उल्लंघन करेगा, तो ढेर संपत्ति को फिर से स्थापित करने के लिए नए रूट (''सिंक'' ऑपरेशन) को छान लें।
+* '''एक्सट्रैक्शन''': रूट को हटा दें और हीप के अंतिम तत्व को रूट में डालें। यदि यह हीप गुण का उल्लंघन करेगा, तो हीप गुण को फिर से स्थापित करने के लिए नए रूट (''सिंक'' ऑपरेशन) को शिफ्ट डाउन करे।
-* प्रतिस्थापन: जड़ को हटा दें और ''नए'' तत्व को जड़ में डालें और छान लें। जब निष्कर्षण के बाद सम्मिलन की तुलना की जाती है, तो यह छानने के कदम से बचता है।
+* '''रिप्लेसमेंट''': रूट को हटा दें और ''नए'' तत्व को रूट में डालें और शिफ्टडाउन करे। जब निष्कर्षण के बाद सम्मिलन की तुलना की जाती है, तो यह छानने के कदम से बचता है।
-तत्वों की दी गई सारणी से बाइनरी (या ''डी''-एरी) ढेर का निर्माण क्लासिक हीप्सोर्ट#वेरिएशन का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें सबसे खराब स्थिति में तुलना की संख्या 2''एन' के बराबर होती है। ' − 2''''<sub>2</sub>(एन) - ई<sub>2</sub>(एन) (बाइनरी ढेर के लिए), जहां एस<sub>2</sub>(एन) एन और ई के द्विआधारी प्रतिनिधित्व के सभी अंकों का योग है<sub>2</sub>(एन) एन के अभाज्य गुणनखंडन में 2 का घातांक है।<ref>{{citation
+तत्वों की दी गई सारणी से एक बाइनरी (या डी-एरी) हीप का निर्माण क्लासिक फ़्लॉइड एल्गोरिदम का उपयोग करके रैखिक समय में किया जा सकता है, जिसमें तुलना की सबसे खराब स्थिति संख्या 2''N'' − 2''s''<sub>2</sub>(''N'') − ''e''<sub>2</sub>(''N'') (एक बाइनरी हीप के लिए) के बराबर है, जहां ''s''<sub>2</sub>(''N'') ''N'' के बाइनरी प्रतिनिधित्व के सभी अंकों का योग है और ''e''<sub>2</sub>(''N'') ''N'' के अभाज्य गुणनखंड में 2 का घातांक है।<ref>{{citation
   | last1 = Suchenek | first1 = Marek A.
   | title = Elementary Yet Precise Worst-Case Analysis of Floyd's Heap-Construction Program
@@ Line 59: / Line 59: @@
   | volume = 120
   | issue = 1
-  | year = 2012}}.</ref> यह मूल रूप से खाली ढेर में लगातार सम्मिलन के अनुक्रम से तेज़ है, जो लॉग-लीनियर है।{{efn|Each insertion takes O(log(''k'')) in the existing size of the heap, thus <math>\sum_{k=1}^n O(\log k)</math>. Since <math>\log n/2 = (\log n) - 1</math>, a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume <math>k = n</math>; formally the time is <math>n O(\log n) - O(n) = O(n \log n)</math>. This can also be readily seen from [[Stirling's approximation]].}}
+  | year = 2012}}.</ref> यह मूल रूप से खाली हीप में लगातार सम्मिलन के अनुक्रम से तेज़ है, जो लॉग-लीनियर है।{{efn|Each insertion takes O(log(''k'')) in the existing size of the heap, thus <math>\sum_{k=1}^n O(\log k)</math>. Since <math>\log n/2 = (\log n) - 1</math>, a constant factor (half) of these insertions are within a constant factor of the maximum, so asymptotically we can assume <math>k = n</math>; formally the time is <math>n O(\log n) - O(n) = O(n \log n)</math>. This can also be readily seen from [[Stirling's approximation]].}}
 ==वेरिएंट==
 {{div col|colwidth=10em}}
-* 2-3 ढेर
+* 2-3 हीप
-* [[बी-ढेर]]
+* [[बी-हीप]]
 *[[बीप]]
-* बाइनरी ढेर
+* बाइनरी हीप
-* [[द्विपद ढेर]]
+* [[द्विपद हीप]]
-* ब्रोडल कतार
+* ब्रोडल क्रम
-* डी-एरी हीप|डी-एरी हीप
+* |डी-एरी हीप
-* [[फाइबोनैचि ढेर]]
+* [[फाइबोनैचि हीप]]
-* [[के-डी ढेर]]
+* [[के-डी हीप]]
-* [[पत्तों का ढेर]]
+* [[पत्तों का हीप]]
 *[[वामपंथी वृक्ष]]
-*[[न्यूनतम-अधिकतम ढेर]]
+*[[न्यूनतम-अधिकतम हीप]]
-* जोड़ी ढेर
+* जोड़ी हीप
-* [[मूलांक ढेर]]
+* [[मूलांक हीप]]
-* [[यादृच्छिक पिघलने योग्य ढेर]]
+* [[यादृच्छिक पिघलने योग्य हीप]]
-*[[तिरछा ढेर]]
+*[[तिरछा हीप]]
-* मुलायम ढेर
+* मुलायम हीप
-* [[टर्नरी ढेर]]
+* [[टर्नरी हीप]]
 * [[जाल बिछाना]]
-* [[कमजोर ढेर]]
+* [[कमजोर हीप]]
 {{div col end}}
@@ Line 91: / Line 91: @@
 हीप डेटा संरचना में कई अनुप्रयोग हैं।
-* हीपसॉर्ट: सर्वोत्तम सॉर्टिंग विधियों में से एक, यथास्थान और बिना किसी द्विघात सबसे खराब स्थिति के।
+*'''हीपसॉर्ट:''' सर्वोत्तम सॉर्टिंग विधियों में से एक, जो कि उपस्थित है और इसमें कोई द्विघात सबसे खराब स्थिति नहीं है।
-* चयन एल्गोरिदम: ढेर निरंतर समय में न्यूनतम या अधिकतम तत्व तक पहुंच की अनुमति देता है, और अन्य चयन (जैसे कि माध्यिका या केटीएच-तत्व) ढेर में मौजूद डेटा पर उप-रेखीय समय में किया जा सकता है।<ref>{{citation
+* '''सिलेक्शन एल्गोरिदम''': हीप निरंतर समय में न्यूनतम या अधिकतम तत्व तक पहुंच की अनुमति देता है, और अन्य चयन (जैसे कि माध्यिका या केटीएच-तत्व) हीप में उपस्थित डेटा पर उप-रेखीय समय में किया जा सकता है।<ref>{{citation
   | last = Frederickson
   | first = Greg N.
@@ Line 110: / Line 110: @@
   | doi-access = free
   }}</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 जेनेरिक हीप कार्यान्वयन] है। यह एसटीएल जैसी एपीआई प्रदान करता है।
+*डी-एरी हीप और बी-हीप समर्थन के साथ 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://dlang.org/phobos/std_container_binaryheap.html सम्मिलित है], जिसे डी के [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}}] मापांक [https://hackage.haskell.org/package/heaps है]।
-* [[जावा (प्रोग्रामिंग भाषा)]] प्लेटफ़ॉर्म (संस्करण 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}}] मॉड्यूल [https://docs.python.org/library/heapq.html है] जो बाइनरी हीप का उपयोग करके प्राथमिकता क्रम लागू करता है। लाइब्रेरी के-वे मर्जिंग का समर्थन करने के लिए हीप्रप्लेस फ़ंक्शन को प्रकाशित करती है।
-* [[PHP]] में अधिकतम-ढेर दोनों हैं ({{mono|SplMaxHeap}}) और न्यूनतम-ढेर ({{mono|SplMinHeap}}) मानक PHP लाइब्रेरी में संस्करण 5.3 के अनुसार।
+*मानक [[PHP|पीएचपी]] लाइब्रेरी में संस्करण 5.3 के अनुसार पीएचपी में मैक्स-हीप ({{mono|SplMaxHeap}}) और न्यूनतम-हीप ({{mono|SplMinHeap}}) दोनों हैं।
-* [[पर्ल]] ने [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://developer.apple.com/library/mac/#documentation/CoreFoundation/Reference/CFBinaryHeapRef/Reference/reference.html सम्मिलित है]।
-* [[फिरौन]] के पास परीक्षण मामलों के सेट के साथ संग्रह-अनुक्रमणीय पैकेज में ढेर का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में ढेर का उपयोग किया जाता है।
+* [[फिरौन]] के पास परीक्षण मामलों के सेट के साथ संग्रह-अनुक्रमणीय पैकेज में हीप का कार्यान्वयन है। टाइमर इवेंट लूप के कार्यान्वयन में हीप का उपयोग किया जाता है।
-* रस्ट (प्रोग्रामिंग भाषा) प्रोग्रामिंग भाषा में बाइनरी मैक्स-हीप कार्यान्वयन है, [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html {{mono|BinaryHeap}}], में {{mono|collections}} इसके मानक पुस्तकालय का मॉड्यूल।
+* रस्ट प्रोग्रामिंग भाषा में इसके मानक लाइब्रेरी के {{mono|collections}} मॉड्यूल में एक बाइनरी मैक्स-हीप कार्यान्वयन, [https://doc.rust-lang.org/std/collections/struct.BinaryHeap.html {{mono|BinaryHeap}}] है।
 * .NET में [https://docs.microsoft.com/dotnet/api/system.collections.generic.priorityqueue-2 प्राथमिकता क्यू] वर्ग है जो क्वाटरनरी (डी-आरी) मिन-हीप कार्यान्वयन का उपयोग करता है। यह .NET 6 से उपलब्ध है।
@@ Line 135: / Line 135: @@
 * [[डेटा संरचना खोजें]]
 * [[स्टैक (सार डेटा प्रकार)]]
-* [[कतार (सार डेटा प्रकार)]]
+* [[कतार (सार डेटा प्रकार)|क्रम (सार डेटा प्रकार)]]
-* वृक्ष (डेटा संरचना)
+* ट्री (डेटा संरचना)
-* ट्रैप, ढेर-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का रूप
+* ट्रैप, हीप-आदेशित पेड़ों पर आधारित बाइनरी सर्च ट्री का रूप
 ==संदर्भ==
@@ Line 153: / Line 153: @@
 {{Data structures}}
-{{DEFAULTSORT:Heap (Data Structure)}}[[Category: ढेर (डेटा संरचनाएं)| ढेर]]
+{{DEFAULTSORT:Heap (Data Structure)}}
+[[Category:Articles with hatnote templates targeting a nonexistent page|Heap (Data Structure)]]
+[[Category:CS1 English-language sources (en)]]
-[[Category: Machine Translated Page]]
+[[Category:Collapse templates|Heap (Data Structure)]]
-[[Category:Created On 10/07/2023]]
+[[Category:Commons category link is locally defined|Heap (Data Structure)]]
+[[Category:Created On 10/07/2023|Heap (Data Structure)]]
+[[Category:Lua-based templates|Heap (Data Structure)]]
+[[Category:Machine Translated Page|Heap (Data Structure)]]
+[[Category:Multi-column templates|Heap (Data Structure)]]
+[[Category:Navigational boxes| ]]
+[[Category:Navigational boxes without horizontal lists|Heap (Data Structure)]]
+[[Category:Pages using div col with small parameter|Heap (Data Structure)]]
+[[Category:Pages with script errors|Heap (Data Structure)]]
+[[Category:Sidebars with styles needing conversion|Heap (Data Structure)]]
+[[Category:Template documentation pages|Documentation/doc]]
+[[Category:Templates Vigyan Ready|Heap (Data Structure)]]
+[[Category:Templates generating microformats|Heap (Data Structure)]]
+[[Category:Templates that add a tracking category|Heap (Data Structure)]]
+[[Category:Templates that are not mobile friendly|Heap (Data Structure)]]
+[[Category:Templates that generate short descriptions|Heap (Data Structure)]]
+[[Category:Templates using TemplateData|Heap (Data Structure)]]
+[[Category:Templates using under-protected Lua modules|Heap (Data Structure)]]
+[[Category:Wikipedia fully protected templates|Div col]]
+[[Category:Wikipedia metatemplates|Heap (Data Structure)]]
+[[Category:ढेर (डेटा संरचनाएं)| ढेर]]

v t e Tree data structures
Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red–black Scapegoat Splay T Treap UB Weight-balanced
Heaps	Binary Binomial Brodal Fibonacci Leftist Pairing Skew van Emde Boas Weak
Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast
Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree PH Priority R Quad R R+ R* Segment VP X
Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

v t e Well-known data structures
Types	Collection Container
Abstract	Associative array Multimap Retrieval Data Structure List Stack Queue Double-ended queue Priority queue Double-ended priority queue Set Multiset Disjoint-set
Arrays	Bit array Circular buffer Dynamic array Hash table Hashed array tree Sparse matrix
Linked	Association list Linked list Skip list Unrolled linked list XOR linked list
Trees	B-tree Binary search tree AA tree AVL tree Red–black tree Self-balancing tree Splay tree Heap Binary heap Binomial heap Fibonacci heap R-tree R* tree R+ tree Hilbert R-tree Trie Hash tree
Graphs	Binary decision diagram Directed acyclic graph Directed acyclic word graph
List of data structures

Anonymous

Search

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

Namespaces

More

Page actions

Latest revision as of 12:11, 28 July 2023

Contents

संचालन

कार्यान्वयन

वेरिएंट

विकल्पों के लिए सैद्धांतिक सीमाओं की तुलना

अनुप्रयोग

प्रोग्रामिंग भाषा कार्यान्वयन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Navigation

Wiki tools

Wiki tools

Anonymous

Search

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

Latest revision as of 12:11, 28 July 2023

संचालन

कार्यान्वयन

वेरिएंट

विकल्पों के लिए सैद्धांतिक सीमाओं की तुलना

अनुप्रयोग

प्रोग्रामिंग भाषा कार्यान्वयन

यह भी देखें

संदर्भ

बाहरी संबंध

Navigation

Wiki tools

Page tools

Other projects

Hidden categories