डीईपीक्यू के लिए सामान्य तरीके

दोहरी ढेर

सिंगल-एंडेड प्रायोरिटी क्यू (PQ) डेटा संरचनाओं से कुशल DEPQ (डबल एंडेड प्रायोरिटी क्यू) डेटा संरचनाओं पर पहुंचने के लिए सामान्य तरीकों का अस्तित्व, जो रिमूव (एनोड) ऑपरेशन का एक कुशल कार्यान्वयन भी प्रदान करता है (यह ऑपरेशन नोड एनोड को समाप्त करता है) पी क्यू)। इन विधियों में सबसे सरल, दोहरी संरचना विधि, न्यूनतम पीक्यू और अधिकतम पीक्यू दोनों का ट्रैक रखती है, जो न्यूनतम पीक्यू के नोड्स और एक ही तत्व से युक्त अधिकतम पीक्यू के बीच पत्राचार पॉइंटर्स से जुड़े सभी डीईपीक्यू तत्वों का है।

चित्रा ए 7, 8, 3, 6, 5 तत्वों के लिए दोहरी ढेर संरचना प्रदर्शित करता है। पत्राचार सूचक लाल तीर के रूप में प्रदर्शित होते हैं।

चित्र A:दोहरा ढेर

हालांकि यह आंकड़ा न्यूनतम और अधिकतम ढेर दोनों में संग्रहीत प्रत्येक तत्व को प्रदर्शित करता है, प्रत्येक तत्व को दो ढेर में से केवल एक में संग्रहीत करना आवश्यक है।

isEmpty और size संचालन एक चर आकार को लागू करके लागू किया जाता है जो DEPQ में तत्वों की संख्या का ट्रैक रखता है। न्यूनतम तत्व न्यूनतम ढेर की जड़ में स्थित है और अधिकतम तत्व अधिकतम ढेर की जड़ में स्थित है। एक तत्व ए डालने के लिए, हम ए को न्यूनतम और अधिकतम ढेर दोनों में डालते हैं और फिर न्यूनतम और अधिकतम ढेर में ए के स्थानों के बीच पत्राचार पॉइंटर्स सेट करते हैं। न्यूनतम तत्व को खत्म करने के लिए, हम न्यूनतम हीप से एक रिमूवमिन करते हैं और एक रिमूव (एनोड) करते हैं, जहां एनोड अधिकतम हीप से हटाए गए तत्व के लिए संबंधित नोड है। अधिकतम तत्व को समान तरीके से हटा दिया जाता है।

कुल और पत्ती पत्राचार

टोटल और लीफ पत्राचार अधिक परिष्कृत पत्राचार तकनीक हैं। इन दोनों तकनीकों में, आधे तत्व न्यूनतम PQ में और अन्य आधे अधिकतम PQ में स्थित होते हैं। जब तत्वों की संख्या विषम होती है, तो एक तत्व बफर में संग्रहीत होता है। यह बफ़र किया गया तत्व या तो PQ का सदस्य नहीं है। कुल पत्राचार तकनीक में, न्यूनतम PQ में प्रत्येक तत्व x को अधिकतम PQ के एक अलग तत्व y के साथ जोड़ा जाता है। (x, y) तत्वों की एक संगत जोड़ी है जैसे कि प्राथमिकता (x) <=प्राथमिकता (y)।

चित्रा बी 11 तत्वों 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11 के लिए कुल पत्राचार ढेर प्रदर्शित करता है। तत्व 10 बफर में है। संबंधित जोड़े लाल तीरों द्वारा प्रदर्शित होते हैं।

चित्र बी:कुल पत्राचार ढेर

पत्ती पत्राचार तकनीक में, न्यूनतम और अधिकतम PQ के प्रत्येक पत्ती तत्व को संबंधित जोड़ी का हिस्सा बनने की आवश्यकता होती है। गैर-पत्ती तत्वों को किसी भी संबंधित जोड़ी में होने की आवश्यकता नहीं है। चित्रा सी एक पत्ता पत्राचार ढेर प्रदर्शित करता है।

चित्रा सी:एक पत्ता पत्राचार ढेर

कुल और पत्ती पत्राचार संरचनाओं को दोहरी संरचनाओं की तुलना में कम जगह की आवश्यकता होती है। हालाँकि, कुल और पत्ती पत्राचार संरचनाओं के लिए DEPQ एल्गोरिदम दोहरी संरचनाओं की तुलना में अधिक जटिल हैं। तीन पत्राचार तकनीकों में से, पत्ती पत्राचार सबसे तेज़ DEPQ पत्राचार संरचना है।

वर्णित पत्राचार तकनीकों में से किसी को लागू करते हुए, हम ढेर, ऊंचाई पक्षपाती वामपंथी पेड़ों और जोड़ीदार ढेर से डीईपीक्यू संरचनाओं तक पहुंच सकते हैं। इन DEQP संरचनाओं में, ऑपरेशन put(x), removeMin(), और removeMax() उपभोग O(log n) समय (n DEPQ में तत्वों की संख्या है, ढेर बाँधने के लिए, यह एक परिशोधन जटिलता है), और शेष DEPQ संचालन O(1) समय का उपभोग करते हैं।