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

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


मिन-मैक्स हीप

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

संरचना

  • स्तर 0 (मिन): रूट - पूरे हीप में **न्यूनतम** तत्व।
  • स्तर 1 (मैक्स): रूट के बच्चे - इनमें से एक पूरे हीप में **अधिकतम** तत्व है।
  • स्तर 2 (मिन): पोते - प्रत्येक अपने सबट्री में न्यूनतम है।
  • स्तर 3 (मैक्स): प्रत्येक अपने सबट्री में अधिकतम है।
  • आदि...

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

औपचारिक गुण

मान लें y मिन-मैक्स हीप में कोई नोड है।

  • यदि y **मिन (सम) स्तर** पर है: `y.key` उस सबट्री में सभी कीज़ में **सबसे छोटा** है जिसकी रूट y है।
  • यदि y **मैक्स (विषम) स्तर** पर है: `y.key` उस सबट्री में सभी कीज़ में **सबसे बड़ा** है जिसकी रूट y है।

मुख्य संचालन और जटिलता

मैक्स-मिन हीप

विपरीत संरचना: रूट पर **अधिकतम**, स्तर 1 पर **न्यूनतम**। समान जटिलता, बस उल्टे क्रम में।

अनुप्रयोग

  • डबल-एंडेड प्रायोरिटी क्यू (DEPQ) कार्यान्वयन।
  • ऐसे परिदृश्य जहां दोनों चरम मानों तक त्वरित पहुंच आवश्यक है (जैसे सिमुलेशन, शेड्यूलिंग)।
  1. सिमेट्रिक मिन-मैक्स हीप्स (SMMH) सिमेट्रिक मिन-मैक्स हीप्स (SMMH)

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

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

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

  1. पेयरिंग हीप पेयरिंग हीप

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

© कॉपीराइट https://in.wsxdn.com सर्वाधिकार सुरक्षित
ऑपरेशनजटिलताविवरण
`getMin()`O(1)रूट तत्व लौटाएं।
`getMax()`O(1)स्तर 1 पर दो नोड्स में से बड़ा लौटाएं।
`insert(x)`O(log n)अंत में डालें, फिर स्तर समता के आधार पर बबल-अप करें (मिन स्तरों के साथ मिन की तुलना, मैक्स के साथ मैक्स)।
`removeMin()`O(log n)रूट हटाएं, अंतिम तत्व से बदलें, ट्रिकल-डाउन (मिन स्तरों पर मिन के साथ तुलना)।
`removeMax()`O(log n)स्तर 1 पर मैक्स हटाएं, अंतिम तत्व से बदलें, ट्रिकल-डाउन।