एक डबल-एंडेड प्राथमिकता कतार (डीईपीक्यू) या डबल-एंडेड हीप को प्राथमिकता कतार या ढेर जैसी डेटा संरचना के रूप में परिभाषित किया जाता है, लेकिन कुंजी या वस्तुओं पर कुछ ऑर्डरिंग के अनुसार अधिकतम और न्यूनतम दोनों को कुशल हटाने की अनुमति देता है। ढांचा। DEPQ में प्रत्येक तत्व प्राथमिकता या मान से जुड़ा होता है। DEPQ में, आरोही और अवरोही दोनों क्रम में तत्वों को हटाना या हटाना संभव है।
संचालन
एक डबल-एंडेड प्राथमिकता कतार में निम्नलिखित ऑपरेशन होते हैं
खाली है ()
यह फ़ंक्शन यह जाँचने के लिए ज़िम्मेदार है कि क्या DEPQ खाली है और खाली होने पर सही है।
आकार ()
यह फ़ंक्शन DEPQ में मौजूद तत्वों की कुल संख्या को वापस करने के लिए ज़िम्मेदार है।
getMin(y)
यह फ़ंक्शन कम से कम प्राथमिकता वाले तत्व y को वापस करने के लिए ज़िम्मेदार है।
getMax(y)
यह फ़ंक्शन सर्वोच्च प्राथमिकता वाले तत्व y को वापस करने के लिए ज़िम्मेदार है।
डालें(y)
यह फ़ंक्शन तत्व y को DEPQ में सम्मिलित करने के लिए ज़िम्मेदार है।
निकालेंन्यूनतम(y)
यह फ़ंक्शन न्यूनतम प्राथमिकता वाले तत्व y को हटाने और इस तत्व को वापस करने के लिए ज़िम्मेदार है।
अधिकतम निकालें(y)
यह फ़ंक्शन अधिकतम प्राथमिकता वाले तत्व y को हटाने और इस तत्व को वापस करने के लिए ज़िम्मेदार है।
कार्यान्वयन
डबल-एंडेड प्राथमिकता कतारों को संतुलित बाइनरी सर्च ट्री (जहां सबसे छोटे और सबसे बड़े तत्वों को क्रमशः सबसे बाईं और सबसे दाईं पत्तियों के रूप में माना जाता है) से बनाया या बनाया जा सकता है, या विशेष डेटा संरचनाओं जैसे न्यूनतम-अधिकतम हीप और पेयरिंग हीप को लागू किया जा सकता है।
सामान्य प्राथमिकता वाली कतारों से डबल-एंडेड प्राथमिकता कतारों पर पहुंचने की सामान्य विधियाँ हैं:
दोहरी संरचना विधि
इस पद्धति के अनुसार, न्यूनतम और अधिकतम के लिए दो अलग-अलग प्राथमिकता वाली कतारें सेट या रखरखाव की जाती हैं। दोनों प्राथमिकता कतारों में समान तत्व पत्राचार संकेतकों की सहायता से प्रदर्शित या दिखाए जाते हैं।
यहां, न्यूनतम और अधिकतम तत्वों को क्रमशः न्यूनतम ढेर और अधिकतम ढेर के रूट नोड्स में निहित मानों के रूप में दर्शाया गया है।
न्यूनतम तत्व निकाला जा रहा है - मिन हीप पर रिमूवमिन () को ऑपरेट करें और मैक्स हीप पर रिमूव (नोड वैल्यू) करें, जहां नोड वैल्यू को मैक्स हीप में संबंधित नोड में वैल्यू के रूप में परिभाषित किया गया है।
अधिकतम तत्व निकाला जा रहा है - मैक्स हीप पर रिमूवमैक्स () को ऑपरेट करें और मिन हीप पर रिमूव (नोड वैल्यू) करें, जहां नोड वैल्यू को मिन हीप में संबंधित नोड में वैल्यू के रूप में परिभाषित किया गया है।
कुल पत्राचार
आधे तत्व न्यूनतम प्राथमिकता कतार में हैं और अन्य आधे अधिकतम प्राथमिकता कतार में हैं। न्यूनतम प्राथमिकता कतार में प्रत्येक तत्व में अधिकतम प्राथमिकता कतार में एक तत्व के साथ एक-से-एक पत्राचार होता है। यदि डीईपीक्यू में तत्वों की संख्या विषम मान इंगित करती है, तो तत्वों में से एक को बफर यानी एक विशिष्ट भंडारण क्षेत्र में रखा जाता है। न्यूनतम प्राथमिकता कतार में प्रत्येक तत्व की प्राथमिकता अधिकतम प्राथमिकता कतार में संबंधित तत्व से कम या उसके बराबर होगी।
पत्ती पत्राचार
इस पद्धति के अनुसार केवल न्यूनतम और अधिकतम प्राथमिकता कतार के पत्ती तत्व एक-से-एक जोड़े के अनुरूप होते हैं। गैर-पत्ती तत्वों के लिए एक-से-एक पत्राचार जोड़ी में होना आवश्यक नहीं है।
अंतराल ढेर
उपर्युक्त पत्राचार विधियों के अलावा, डीईपीक्यू को पूरी तरह से अंतराल ढेर को लागू करने के लिए प्राप्त किया जा सकता है। एक अंतराल ढेर एक एम्बेडेड न्यूनतम-अधिकतम ढेर की तरह होता है जिसमें प्रत्येक नोड में दो तत्व होते हैं। इसे एक पूर्ण बाइनरी ट्री के रूप में परिभाषित किया गया है जिसमें -
- बायां तत्व हमेशा दाएं तत्व से छोटा या बराबर होता है।
- दोनों तत्व एक बंद अंतराल को परिभाषित या निर्दिष्ट करते हैं।
- रूट को छोड़कर किसी भी नोड द्वारा दर्शाए गए अंतराल को मूल नोड के उप-अंतराल के रूप में दर्शाया जाता है।
- बाईं ओर के तत्व एक न्यूनतम ढेर को परिभाषित या निरूपित करते हैं।
- दाईं ओर के तत्व अधिकतम ढेर को परिभाषित या निरूपित करते हैं।