डबल-एंडेड प्रायोरिटी क्यू (DEPQ) के लिए सामान्य विधियाँ
डबल-एंडेड प्रायोरिटी क्यू (DEPQ) एक डेटा संरचना है जो न्यूनतम और अधिकतम दोनों तत्वों तक कुशल पहुंच और विलोपन की अनुमति देती है। सिंगल-एंडेड प्रायोरिटी क्यू (PQ) से कुशल DEPQ संरचनाएं बनाने के लिए तीन मुख्य सामान्य विधियाँ हैं, बशर्ते PQ एक कुशल `remove(node)` ऑपरेशन का समर्थन करे।
1. डुअल स्ट्रक्चर मेथड (डुअल हीप)
सबसे सरल विधि: एक मिन-PQ और एक मैक्स-PQ दोनों को बनाए रखें, जिसमें समान तत्वों के नोड्स के बीच **कॉरेस्पॉन्डेंस पॉइंटर्स** हों।
- स्पेस: 2n (प्रत्येक तत्व दोनों हीप्स में संग्रहीत), हालांकि अनुकूलन संभव है (प्रत्येक तत्व केवल एक हीप में)।
- ऑपरेशन्स:
- `getMin()`/`getMax()`: O(1) (संबंधित हीप की रूट)।
- `put(x)`: दोनों हीप्स में डालें, कॉरेस्पॉन्डेंस पॉइंटर सेट करें → O(log n)।
- `removeMin()`: मिन-हीप से `removeMin()`, मैक्स-हीप से कॉरेस्पॉन्डिंग नोड पर `remove(node)` → O(log n)।
- `removeMax()`: सममित।
2. टोटल कॉरेस्पॉन्डेंस
आधे तत्व मिन-PQ में, आधे मैक्स-PQ में। यदि तत्वों की संख्या विषम है, तो एक तत्व बफर में रहता है।
- मिन-PQ में प्रत्येक तत्व x का मैक्स-PQ में एक विशिष्ट तत्व y के साथ एक-से-एक कॉरेस्पॉन्डेंस होता है, जहां `priority(x) ≤ priority(y)`।
- स्पेस: ~n (डुअल स्ट्रक्चर से बेहतर)।
- जटिलता: एल्गोरिदम अधिक जटिल हैं।
3. लीफ कॉरेस्पॉन्डेंस
केवल मिन-PQ और मैक्स-PQ के **लीफ नोड्स** कॉरेस्पॉन्डिंग जोड़े बनाते हैं। नॉन-लीफ नोड्स को कॉरेस्पॉन्डेंस की आवश्यकता नहीं होती।
- स्पेस: ~n।
- प्रदर्शन: तीनों में से सबसे तेज़ DEPQ कॉरेस्पॉन्डेंस संरचना।
- जटिलता: कार्यान्वयन सबसे जटिल।
समर्थित आधार संरचनाएं और जटिलता
इन तकनीकों को लागू किया जा सकता है:
- हीप्स (बाइनरी हीप्स)
- हाइट-बायस्ड लेफ्टिस्ट ट्रीज़
- पेयरिंग हीप्स
समय जटिलता
| ऑपरेशन | हीप्स / लेफ्टिस्ट ट्रीज़ | पेयरिंग हीप्स |
|---|---|---|
| `put(x)`, `removeMin()`, `removeMax()` | O(log n) | O(log n) परिशोधित |
| `isEmpty()`, `size()`, `getMin()`, `getMax()` | O(1) | O(1) |
