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

डबल-एंडेड प्रायोरिटी क्यू (DEPQ): परिभाषा, संचालन और कार्यान्वयन


डबल-एंडेड प्रायोरिटी क्यू (DEPQ)

एक **डबल-एंडेड प्रायोरिटी क्यू (DEPQ)** एक डेटा संरचना है जो एक प्रायोरिटी क्यू की तरह व्यवहार करती है लेकिन संग्रहीत कुंजियों/आइटम्स पर किसी क्रम के अनुसार **न्यूनतम और अधिकतम दोनों तत्वों के कुशल विलोपन** की अनुमति देती है।

DEPQ में प्रत्येक तत्व की एक प्राथमिकता/मान होता है। तत्वों को आरोही और अवरोही दोनों क्रम में हटाया जा सकता है।

मुख्य संचालन

कार्यान्वयन दृष्टिकोण

1. बैलेंस्ड बाइनरी सर्च ट्रीज़ (BBST)

  • सबसे छोटा = लेफ्टमोस्ट लीफ, सबसे बड़ा = राइटमोस्ट लीफ।
  • सभी ऑपरेशन्स O(log n)।
  • उदाहरण: AVL ट्री, रेड-ब्लैक ट्री, `std::map`/`std::set`।

2. विशेष संरचनाएं

  • मिन-मैक्स हीप (ऊपर देखें)।
  • पेयरिंग हीप (DEPQ के लिए अनुकूलित)।
  • इंटरवल हीप (नीचे देखें)।
  • डिएप (Deap)।
  • सिमेट्रिक मिन-मैक्स हीप (SMMH)।

सामान्य परिवर्तन विधियाँ (सामान्य PQ → DEPQ)

डुअल स्ट्रक्चर मेथड

दो अलग-अलग PQs बनाए रखें: एक मिन-PQ, एक मैक्स-PQ। समान तत्वों को **कॉरेस्पॉन्डेंस पॉइंटर्स** से लिंक करें।

  • `getMin()`/`getMax()`: संबंधित रूट → O(1)।
  • `removeMin()`: मिन-PQ पर `removeMin()`, मैक्स-PQ पर कॉरेस्पॉन्डिंग नोड पर `remove(node)`।
  • `removeMax()`: सममित।

टोटल कॉरेस्पॉन्डेंस

  • आधे तत्व मिन-PQ में, आधे मैक्स-PQ में।
  • मिन-PQ में प्रत्येक तत्व का मैक्स-PQ में एक विशिष्ट कॉरेस्पॉन्डेंट होता है: `priority(min) ≤ priority(max)`।
  • विषम गिनती → एक तत्व बफर में।
  • स्पेस: ~n (डुअल से बेहतर)।

लीफ कॉरेस्पॉन्डेंस

  • केवल **लीफ नोड्स** कॉरेस्पॉन्डिंग जोड़े बनाते हैं।
  • नॉन-लीफ नोड्स के कॉरेस्पॉन्डेंट्स की आवश्यकता नहीं।
  • सबसे तेज़ DEPQ कॉरेस्पॉन्डेंस संरचना, लेकिन सबसे जटिल एल्गोरिदम।

इंटरवल हीप्स

प्रत्येक नोड में दो तत्व `[a, b]` होते हैं जहां `a ≤ b`:

  • लेफ्ट एंडपॉइंट्स → मिन-हीप।
  • राइट एंडपॉइंट्स → मैक्स-हीप।
  • नॉन-रूट नोड्स का अंतराल पैरेंट का सब-इंटरवल होता है।
  • कॉम्पैक्ट, सरणी-आधारित, O(log n) संचालन।
  1. C में लिंक्ड लिस्ट का उपयोग करके प्रायोरिटी क्यू (Priority Queue) C में लिंक्ड लिस्ट का उपयोग करके प्रायोरिटी क्यू (Priority Queue)

    हमें डेटा और पूर्णांक मान के रूप में प्राथमिकता दी गई है और कार्य दी गई प्राथमिकता के अनुसार एक लिंक्ड लिस्ट बनाना और परिणाम प्रदर्शित करना है। क्यू एक FIFO डेटा संरचना है जिसमें पहले डाला गया तत्व हटाया जाने वाला पहला होता है। एक प्रायोरिटी क्यू एक प्रकार की क्यू है जिसमें तत्वों को प्राथमिकता के

  1. C++ STL में प्राथमिकता कतार (Priority Queue) C++ STL में प्राथमिकता कतार (Priority Queue)

    प्राथमिकता कतार प्राथमिकता वाले तत्वों के संग्रह को संग्रहीत करने के लिए एक अमूर्त डेटा प्रकार है जो उनकी प्राथमिकताओं के आधार पर एक तत्व के सम्मिलन और विलोपन का समर्थन करता है, अर्थात् पहली प्राथमिकता वाले तत्व को किसी भी समय हटाया जा सकता है। प्राथमिकता कतार स्टैक, कतार, सूची आदि की तरह अपने स्थान

  1. C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार C++ में डबल लिंक्ड लिस्ट का उपयोग करके प्राथमिकता कतार

    हमें डेटा और प्राथमिकता एक पूर्णांक मान के रूप में दी गई है और कार्य दिए गए प्राथमिकता के अनुसार डबल लिंक्ड लिस्ट बनाना और परिणाम प्रदर्शित करना है।कतार एक FIFO डेटा संरचना है जिसमें पहले डाला गया तत्व सबसे पहले हटाया जाता है। प्राथमिकता कतार एक प्रकार की कतार है जिसमें तत्वों को प्राथमिकता के आधार

© कॉपीराइट https://in.wsxdn.com सर्वाधिकार सुरक्षित
ऑपरेशनविवरण
`isEmpty()`जांचें कि DEPQ खाली है या नहीं।
`size()`तत्वों की संख्या लौटाएं।
`getMin()`न्यूनतम प्राथमिकता वाला तत्व लौटाएं।
`getMax()`अधिकतम प्राथमिकता वाला तत्व लौटाएं।
`put(x)`तत्व x डालें।
`removeMin()`न्यूनतम प्राथमिकता वाला तत्व हटाएं और लौटाएं।
`removeMax()`अधिकतम प्राथमिकता वाला तत्व हटाएं और लौटाएं।