यह आलेख आपको ढेर प्रकार के काम का पूरा अवलोकन देगा और बाद में हम जावा में एक बाइनरी हीप को लागू करना सीखेंगे।
यहाँ इस लेख के लिए एजेंडा है:
चलो शुरू करें!
ढेर की तरह क्या है?
हीप मूल रूप से एक पेड़ आधारित डेटा संरचना है। यह नोड्स है। नोड में कुछ तत्व शामिल होते हैं। प्रत्येक नोड में एक तत्व होता है।
नोड्स में बच्चे हो सकते हैं। यदि कोई संतान नहीं है, तो इसे पत्ती कहा जाता है।
इसके दो नियम हैं:
- प्रत्येक नोड का मान उसके बच्चों में संग्रहीत सभी मूल्यों से कम या बराबर होना चाहिए।
- इसकी कम से कम संभव ऊंचाई है।
ढेर निकालने में बेहद कुशल हैंकम से कम या सबसे बड़ा तत्व।
चलिए अब मिन हीप पर चलते हैं!
मिन हीप
मिन हीप एक सम्पूर्ण बाइनरी ट्री है, जिसमें मूल तत्व का मूल्य बाल तत्व की तुलना में कम या बराबर होता है।
न्यूनतम ढेर का प्रतिनिधित्व
Arr [(i-1) / 2]: यह मूल नोड लौटाएगा।
Arr [(2 * i) + 1]: यह बाएं बच्चे का नोड लौटाएगा।
Arr [(2 * i) + 2]: यह सही बच्चा नोड लौटाएगा।
मिन हीप के कुछ तरीके हैं:
- सम्मिलित करें (): पेड़ के अंत में एक नई कुंजी जोड़ी जाती है। यदि नई कुंजी बड़ी है तो अभिभावक, फिर कुछ भी करने की आवश्यकता नहीं है, अन्यथा, हमें ढेर संपत्ति स्थापित करने के लिए पार करना होगा।
- getMin (): यह विधि मूल तत्व को वापस करने में मदद करती है।
- अर्कमीन (): यह विधि न्यूनतम लौटाती हैतत्व।
अब मैक्स हीप पर चल रहा है।
मैक्स ढेर
मैक्स हीप एक सम्पूर्ण बाइनरी ट्री है जिसमें जड़ तत्व का मूल्य बाल तत्व की तुलना में अधिक या बराबर होता है।
मैक्स हीप में कई तरीके भी होते हैं!
- सम्मिलित करें (): यह ढेर में एक तत्व सम्मिलित करेगा।
- हटाएं () : यह ढेर से एक तत्व को हटा देगा।
- FindMax (): यह ढेर से अधिकतम तत्व प्राप्त करेगा।
- प्रिंटहाइप (): यह ढेर की सामग्री को मुद्रित करेगा
अब मैं आपको एक चित्र और बाद में एक जावा के माध्यम से ढेर कार्यान्वयन दिखाता हूंकोड।
जावा में ढेर कार्यान्वयन
आरेख:
कैसे जावा में गतिशील सरणी बनाने के लिए
ऊपर दिया गया आरेख जावा में बाइनरी हीप को दर्शाता है। जैसा कि आप जान चुके हैं कि दो ढेर हैं: मिन हीप और मैक्स हीप, यहाँ एक आरेख है:
अब, अपने अगले सेगमेंट पर चलते हुए, हम देखेंगे कि जावा में एक बाइनरी हीप को कैसे लागू किया जाए।
कोड:
पब्लिक क्लास बाइनरीहीप {प्राइवेट स्टैटिक फाइनल इंट डी = 2 प्राइवेट इंट [] ढेर प्राइवेट इंट हीपसाइज / ** * यह हमारे हीप को डिफॉल्ट साइज के साथ इनिशियलाइज़ करेगा। * (पब्लिक बाइनरीहीप (इंट क्षमता) {heapSize = 0 heap = new int [क्षमता + 1] Arrays.fill (हीप, -1)} / ** * यह जांच करेगा कि क्या हीप खाली है या नहीं * जटिलता: O ( 1) * / सार्वजनिक बूलियन isEmpty () {वापसी heapSize == 0} / ** * यह जांच करेगा कि क्या ढेर भरा है या नहीं * जटिलता: O (1) * / सार्वजनिक बूलियन isFull () {वापसी heapSize == हीप .length} निजी int माता-पिता (int i) {वापसी (i-1) / d} निजी int kthChild (int i, int k) {वापसी d * i + k} / ** * यह ढेर करने के लिए नया तत्व डालेगा * जटिलता: O (लॉग एन) * सबसे खराब स्थिति के रूप में, हमें रूट * / सार्वजनिक शून्य डालने (int x) {यदि (isFull ()) नए NoSuchElementException ('ढेर पूरा) फेंकने की आवश्यकता है, तो सम्मिलित करने के लिए कोई स्थान नहीं है। नया तत्व ') हीप [heapSize ++] = x heapifyUp (heapSize-1)} / ** * यह सूचकांक x पर तत्व को हटा देगा * जटिलता: O (लॉग एन) * * / पब्लिक इंट डिलीट (int x) {if (isEmpty ()) नया NoSuchElementException फेंकें ('हीप खाली है, डिलीट करने का कोई तत्व नहीं है') int key = heap [x] हीप [x] = हीप [heapSize -1] heapSize-- heapifybown (x) retu rn कुंजी} / ** * यह विधि किसी तत्व को सम्मिलित करते समय ढेर संपत्ति को बनाए रखने के लिए उपयोग की जाती है। * * / निजी शून्य heapifyUp (int i) {int temp = heap [i] जबकि (i> 0 && temp> heap [माता-पिता (i)]) {ढेर [i] = हीप [माता-पिता (i] i = माता-पिता (i)} हीप [i] = temp} / ** * यह विधि किसी तत्व को हटाते समय हीप संपत्ति को बनाए रखने के लिए उपयोग की जाती है। * (/ निजी शून्य heapifyDown (int i) {int child int temp = heap [i] जबकि (kthChild (i, 1))हीप [राइटहिल्ड]; बाएं चिल्ड्रन: राइटचाइल्ड} / ** * * यह विधि हीप के सभी तत्व को प्रिंट करने के लिए उपयोग किया जाता है * * / सार्वजनिक शून्य प्रिंटहाइप () {System.out.print ('nHeap =) के लिए (int i = 0 i)इसके साथ, हम जावा में बाइनरी हीप पर इस लेख के अंत में आते हैं। इसकी जाँच पड़ताल करो 250,000 से अधिक संतुष्ट शिक्षार्थियों के एक नेटवर्क के साथ एक विश्वसनीय ऑनलाइन शिक्षण कंपनी, एडुरेका द्वारा, दुनिया भर में फैली हुई है। एडुर्का के जावा जे 2 ईई और एसओए प्रशिक्षण और प्रमाणन पाठ्यक्रम उन छात्रों और पेशेवरों के लिए डिज़ाइन किया गया है जो जावा डेवलपर बनना चाहते हैं। पाठ्यक्रम आपको जावा प्रोग्रामिंग में एक शुरुआत देने के लिए डिज़ाइन किया गया है और आपको हाइबरनेट और स्प्रिंग जैसे विभिन्न जावा फ्रेमवर्क के साथ कोर और उन्नत जावा अवधारणाओं दोनों के लिए प्रशिक्षित करता है।
क्या आप हमसे कोई प्रश्न पूछना चाहते हैं? कृपया इस 'जावा ArrayList' ब्लॉग के टिप्पणी अनुभाग में उल्लेख करें और हम जल्द से जल्द आपके पास वापस आ जाएंगे।