একটি ডাবল-এন্ডেড প্রায়োরিটি কিউ (DEPQ) বা ডাবল-এন্ডেড হিপকে অগ্রাধিকার সারি বা স্তূপের মতো ডেটা স্ট্রাকচার হিসাবে সংজ্ঞায়িত করা হয়, তবে এতে সঞ্চিত কী বা আইটেমগুলির কিছু ক্রম অনুসারে সর্বাধিক এবং সর্বনিম্ন উভয়েরই দক্ষ অপসারণের অনুমতি দেয় গঠন. DEPQ-এর প্রতিটি উপাদান একটি অগ্রাধিকার বা মানের সাথে যুক্ত। একটি DEPQ-তে, ঊর্ধ্বগামী এবং অবরোহ উভয় ক্রমে উপাদানগুলিকে বাদ দেওয়া বা অপসারণ করা সম্ভব৷
অপারেশন
একটি ডবল-এন্ডেড অগ্রাধিকার সারিতে নিম্নলিখিত ক্রিয়াকলাপগুলি রয়েছে
খালি()
এই ফাংশনটি DEPQ খালি কিনা তা পরীক্ষা করার জন্য দায়ী এবং খালি থাকলে সত্য ফেরত দেয়৷
আকার()
এই ফাংশনটি DEPQ-এ উপস্থিত মোট উপাদানের সংখ্যা ফেরত দেওয়ার জন্য দায়ী।
getMin(y)
এই ফাংশনটি y উপাদানটিকে ন্যূনতম অগ্রাধিকার দেওয়ার জন্য দায়ী৷
৷getMax(y)
এই ফাংশনটি সবচেয়ে বেশি অগ্রাধিকারের উপাদান y ফেরত দেওয়ার জন্য দায়ী৷
৷পুট(y)
এই ফাংশনটি DEPQ এ y উপাদান সন্নিবেশ করার জন্য দায়ী।
রিমুভমিন(y)
এই ফাংশনটি ন্যূনতম অগ্রাধিকার সহ একটি উপাদান y সরাতে এবং এই উপাদানটি ফিরিয়ে দেওয়ার জন্য দায়ী৷
ম্যাক্স(y) সরান
এই ফাংশনটি সর্বাধিক অগ্রাধিকার সহ একটি উপাদান y অপসারণ করতে এবং এই উপাদানটি ফিরিয়ে দেওয়ার জন্য দায়ী৷
বাস্তবায়ন
ডাবল-এন্ডেড অগ্রাধিকার সারিগুলি সুষম বাইনারি অনুসন্ধান গাছ থেকে তৈরি বা তৈরি করা যেতে পারে (যেখানে সবচেয়ে ছোট এবং বৃহত্তম উপাদানগুলিকে যথাক্রমে বাম এবং ডানদিকের পাতা হিসাবে বিবেচনা করা হয়), বা ন্যূনতম-ম্যাক্স হিপ এবং পেয়ারিং হিপের মতো বিশেষ ডেটা স্ট্রাকচার বাস্তবায়ন করা যেতে পারে।
সাধারণ অগ্রাধিকার সারি থেকে ডবল-এন্ডেড অগ্রাধিকার সারিগুলিতে পৌঁছানোর সাধারণ পদ্ধতিগুলি হল:
দ্বৈত গঠন পদ্ধতি
এই পদ্ধতি অনুসারে, ন্যূনতম এবং সর্বোচ্চের জন্য দুটি ভিন্ন অগ্রাধিকার সারি সেট বা বজায় রাখা হয়। উভয় অগ্রাধিকার সারিতে একই উপাদানগুলি চিঠিপত্র পয়েন্টারের সাহায্যে প্রদর্শিত বা দেখানো হয়৷
এখানে, ন্যূনতম এবং সর্বোচ্চ উপাদানগুলি যথাক্রমে মিন হিপ এবং সর্বোচ্চ হিপের রুট নোডগুলিতে থাকা মান হিসাবে চিহ্নিত করা হয়৷
মিনিট উপাদান সরানো হচ্ছে − মিন হিপে রিমুমিন() চালান এবং সর্বোচ্চ হিপে রিমুভ করুন(নোডের মান), যেখানে নোডের মান সর্বোচ্চ হিপে সংশ্লিষ্ট নোডের মান হিসাবে সংজ্ঞায়িত করা হয়।
সর্বাধিক উপাদান সরানো হচ্ছে − সর্বোচ্চ হিপে রিমুম্যাক্স() পরিচালনা করুন এবং মিন হিপে রিমুভ করুন(নোডের মান), যেখানে নোডের মানটি মিন হিপে সংশ্লিষ্ট নোডের মান হিসাবে সংজ্ঞায়িত করা হয়৷
মোট চিঠিপত্র
অর্ধেক উপাদান ন্যূনতম অগ্রাধিকার সারিতে এবং বাকি অর্ধেক সর্বাধিক অগ্রাধিকার সারিতে। ন্যূনতম অগ্রাধিকার সারির প্রতিটি উপাদানের সর্বাধিক অগ্রাধিকার সারিতে একটি উপাদানের সাথে এক থেকে এক চিঠিপত্র রয়েছে৷ যদি DEPQ-এ উপাদানের সংখ্যা বিজোড় মান নির্দেশ করে, তাহলে উপাদানগুলির একটি বাফারে অর্থাৎ একটি নির্দিষ্ট স্টোরেজ এলাকায় রাখা হয়। ন্যূনতম অগ্রাধিকার সারির প্রতিটি উপাদানের অগ্রাধিকার সর্বোচ্চ অগ্রাধিকার সারিতে সংশ্লিষ্ট উপাদানের চেয়ে কম বা সমান হবে৷
পাতার চিঠিপত্র
এই পদ্ধতি অনুসারে ন্যূনতম এবং সর্বোচ্চ অগ্রাধিকারের সারির পাতার উপাদানগুলি এক থেকে এক জোড়া অনুরূপ গঠন করে। পাতাবিহীন উপাদানগুলির জন্য এক-থেকে-ওয়ান চিঠিপত্রের জোড়ায় থাকা আবশ্যক নয়৷
ইন্টারভাল হিপস
উপরে উল্লিখিত চিঠিপত্রের পদ্ধতিগুলি ছাড়াও, ডিইপিকিউগুলি ব্যবধানের স্তুপগুলিকে পুরোপুরি প্রয়োগ করে প্রাপ্ত করা যেতে পারে। একটি ইন্টারভাল হিপ হল একটি এমবেডেড মিন-ম্যাক্স হিপের মত যাতে প্রতিটি নোড দুটি উপাদান নিয়ে গঠিত। এটিকে একটি সম্পূর্ণ বাইনারি গাছ হিসাবে সংজ্ঞায়িত করা হয় যার মধ্যে −
- বাম উপাদান সর্বদা ডান উপাদানের চেয়ে কম বা সমান।
- উভয় উপাদানই একটি বন্ধ ব্যবধানকে সংজ্ঞায়িত করে বা নির্দিষ্ট করে।
- মূল ব্যতীত যেকোনো নোড দ্বারা উপস্থাপিত ব্যবধানকে প্যারেন্ট নোডের একটি উপ-ব্যবধান হিসাবে চিহ্নিত করা হয়।
- বাম দিকের উপাদানগুলি একটি মিন হিপকে সংজ্ঞায়িত করে বা নির্দেশ করে৷ ৷
- ডান দিকের উপাদানগুলি সর্বাধিক হিপকে সংজ্ঞায়িত করে বা নির্দেশ করে৷ ৷
