Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> प्रोग्रामिंग

पेयरिंग हीप


पेयरिंग हीप को एक प्रकार के हीप डेटा स्ट्रक्चर के रूप में परिभाषित किया जाता है जिसमें अपेक्षाकृत आसान कार्यान्वयन और उत्कृष्ट व्यावहारिक एमोर्टाइज़्ड प्रदर्शन होता है।

पेयरिंग हीप हीप-ऑर्डर्ड मल्टीवे ट्री स्ट्रक्चर हैं, और इन्हें सरलीकृत फाइबोनैचि हीप के रूप में दर्शाया जा सकता है।

इन्हें प्रिम के MST एल्गोरिदम जैसे एल्गोरिदम को लागू करने के लिए एक "मजबूत विकल्प" माना जाता है, और निम्नलिखित ऑपरेशन्स को सपोर्ट करते हैं (मिन-हीप मानकर):

  • find-min - यह फ़ंक्शन हीप के शीर्ष एलिमेंट को वापस करने के लिए जिम्मेदार है।
  • meld - यह फ़ंक्शन दो रूट एलिमेंट्स की तुलना करने के लिए जिम्मेदार है, छोटा परिणाम का रूट बना रहता है, बड़ा एलिमेंट और उसका सबट्री इस रूट के चाइल्ड के रूप में जुड़ जाता है।
  • insert - यह फ़ंक्शन इन्सर्ट किए गए एलिमेंट के लिए एक नया हीप बनाने और उसे मूल हीप में मिलाने के लिए जिम्मेदार है।
  • decrease-key (वैकल्पिक) - यह फ़ंक्शन घटाए जाने वाली की पर रूटेड सबट्री को हटाने, की को छोटी की से बदलने, फिर परिणाम को वापस हीप में मिलाने के लिए जिम्मेदार है।
  • delete-min - यह फ़ंक्शन रूट को हटाने और उसके सबट्रीज के बार-बार मर्ज करने के लिए जिम्मेदार है जब तक कि एक ट्री न रह जाए। विभिन्न मर्जिंग रणनीतियों का उपयोग किया जाता है।
  • प्रत्येक नोड में लेफ्ट चाइल्ड की ओर एक पॉइंटर होता है और लेफ्ट चाइल्ड चाइल्ड के अगले सिबलिंग की ओर इशारा करता है।
  • पेयरिंग हीप का उदाहरण नीचे दिया गया है:

पेयरिंग हीप

पेयरिंग हीप के समय जटिलता का विश्लेषण मुख्य रूप से स्प्ले ट्रीज द्वारा प्रेरित था। प्रति डिलीट-मिन एमोर्टाइज़्ड समय O(log n) माना जाता है, और find-min, meld, और insert ऑपरेशन्स O(1) एमोर्टाइज़्ड समय में चलते हैं।

  1. मिन-मैक्स हीप्स: संरचना, गुण और संचालन मिन-मैक्स हीप्स: संरचना, गुण और संचालन

    मिन-मैक्स हीप एक मिन-मैक्स हीप एक पूर्ण बाइनरी ट्री है जिसमें वैकल्पिक मिन (सम) और मैक्स (विषम) स्तर होते हैं। रूट स्तर 0 (मिन स्तर) पर होता है। संरचना स्तर 0 (मिन): रूट - पूरे हीप में **न्यूनतम** तत्व। स्तर 1 (मैक्स): रूट के बच्चे - इनमें से एक पूरे हीप में **अधिकतम** तत्व है। स्तर 2 (मिन): पोते

  1. सिमेट्रिक मिन-मैक्स हीप्स (SMMH) सिमेट्रिक मिन-मैक्स हीप्स (SMMH)

    सिमेट्रिक मिन-मैक्स हीप (SMMH) एक **सिमेट्रिक मिन-मैक्स हीप (SMMH)** एक पूर्ण बाइनरी ट्री है जिसमें: **रूट खाली** होता है (कोई तत्व नहीं)। प्रत्येक अन्य नोड में **ठीक एक तत्व** होता है। कुल नोड्स = `m + 1` (जहां `m` तत्वों की संख्या है)। संरचनात्मक गुण किसी भी नोड y के लिए जिसके सबट्री में तत्व

  1. पेयरिंग हीप के प्रकार पेयरिंग हीप के प्रकार

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