ডাবল-এন্ডেড প্রায়োরিটি কিউ (DEPQ)

একটি ডাবল-এন্ডেড প্রায়োরিটি কিউ (DEPQ) বা ডাবল-এন্ডেড হিপ হলো একটি ডেটা স্ট্রাকচার যা প্রায়োরিটি কিউ বা হিপের মতো কিন্তু স্ট্রাকচারে সংরক্ষিত কী বা আইটেমের ওয়ার্ডারিং অনুযায়ী দক্ষতার সাথে ম্যাক্সিমাম এবং মিনিমাম উভয়ই রিমুভ করার অনুমতি দেয়। DEPQ-তে প্রতিটি এলিমেন্ট একটি প্রায়োরিটি বা ভ্যালু সাথে যুক্ত থাকে। একটি DEPQ-তে এলিমেন্টগুলো উভয় आरোহী এবং অवरোহী ক্রমে রিমুভ বা সরানো সম্ভব।

অপারেশন

একটি ডাবল-এন্ডেড প্রায়োরিটি কিউ নিম্নলিখিত অপারেশনগুলো নিয়ে গঠিত:

isEmpty()

এই ফাংশন চেক করে DEPQ খালি কিনা এবং খালি হলে true রিটার্ন করে।

size()

এই ফাংশন DEPQ-তে উপস্থিত মোট এলিমেন্টের সংখ্যা রিটার্ন করে।

getMin(y)

এই ফাংশন সবচেয়ে কম প্রায়োরিটিভালো এলিমেন্ট y রিটার্ন করে।

getMax(y)

এই ফাংশন সবচেয়ে বেশি প্রায়োরিটিভালো এলিমেন্ট y রিটার্ন করে।

put(y)

এই ফাংশন এলিমেন্ট y কে DEPQ-তে ইনসার্ট করে।

removeMin(y)

এই ফাংশন ন্যূনতম প্রায়োরিটিভালো এলিমেন্ট y সরিয়ে তা রিটার্ন করে।

removeMax(y)

এই ফাংশন সর্বোচ্চ প্রায়োরিটিভালো এলিমেন্ট y সরিয়ে তা রিটার্ন করে।

অনুপ্রবেশ

ডাবল-এন্ডেড প্রায়োরিটি কিউগুলো बैলেন্সড বাইনারি সার্চ ট্রি থেকে তৈরি করা যেতে পারে (যেখানে সবচেয়ে ছোট এবং সবচেয়ে বড় এলিমেন্ট ক्रमশः লেফটমোস্ট এবং রাইটমোস্ট লিফ হিসেবে বিবেচনা করা হয়), অথবা মিন-ম্যাক্স হিপ এবং পেয়ারিং হিপের মতো স্পেশালাইজড ডেটা স্ট্রাকচার ব্যবহার করে।

নরমাল প্রায়োরিটি কিউ থেকে ডাবল-এন্ডেড প্রায়োরিটি কিউ তৈরি করার জেনেরিক মেথডগুলো:

ডুয়াল স্ট্রাকচার মেথড

এই মেথড অনুযায়ী, মিন এবং ম্যাক্স জন্য দুটি আলাদা প্রায়োরিটি কিউ রক্ষা করা হয়। উভয় প্রায়োরিটি কিউতে একই এলিমেন্টগুলো করেসপন্ডেন্স পয়েন্টার দিয়ে দেখানো হয়।

এখানে, মিনিমাম এবং ম্যাক্সিমাম এলিমেন্টগুলো মিন হিপ এবং ম্যাক্স হিপের রুট নোডে থাকা ভ্যালু হিসেবে দেখানো হয়।

মিন এলিমেন্ট সরানো - মিন হিপে removemin() অপারেট করুন এবং ম্যাক্স হিপে remove(node value) অপারেট করুন, যেখানে node value হলো ম্যাক্স হিপে করেসপন্ডিং নোডের ভ্যালু।

ম্যাক্স এলিমেন্ট সরানো - ম্যাক্স হিপে removemax() অপারেট করুন এবং মিন হিপে remove(node value) অপারেট করুন, যেখানে node value হলো মিন হিপে করেসপন্ডিং নোডের ভ্যালু।

টোটাল করেসপন্ডেন্স

অর্ধেক এলিমেন্ট মিন প্রায়োরিটি কিউতে এবং বাকি অর্ধেক ম্যাক্স প্রায়োরিটি কিউতে থাকে। মিন প্রায়োরিটি কিউ-র প্রতিটি এলিমেন্ট ম্যাক্স প্রায়োরিটি কিউ-র একটি এলিমেন্টের সাথে one-to-one করেসপন্ডেন্স রাখে। যদি DEPQ-তে এলিমেন্টের সংখ্যা বিজোড় হয়, তবে একটি এলিমেন্ট একটি বাফারে রাখা হয় অর্থাৎ একটি নির্দিষ্ট স্টোরেজ এলাকায়। মিন প্রায়োরিটি কিউ-র প্রতিটি এলিমেন্টের প্রায়োরিটি 그에 করেসপন্ডিং ম্যাক্স প্রায়োরিটি কিউ-র এলিমেন্ট থেকে কম বা সমান হবে।

লিফ করেসপন্ডেন্স

এই মেথড অনুযায়ী শুধু মিন এবং ম্যাক্স প্রায়োরিটি কিউর লিফ এলিমেন্টগুলো one-to-one করেসপন্ডিং পেয়ার গঠন করে। নন-লিফ এলিমেন্টগুলোর one-to-one করেসপন্ডেন্স পেয়ারে থাকা আবশ্যক নয়।

ইন্টারভাল হিপ

উপরোক্ত করেসপন্ডেন্স মেথডগুলোর পাশাপাশি, DEPQ ইন্টারভাল হিপ ব্যবহার করে পূর্ণভাবে প্রাপ্ত করা যেতে পারে। একটি ইন্টারভাল হিপ একটি এম্বেডেড মিন-ম্যাক্স হিপের মতো যাতে প্রতিটি নোডে দুটি এলিমেন্ট থাকে। এটি একটি কমপ্লিট বাইনারি ট্রি হিসেবে সংজ্ঞায়িত হয় যাতে:

• বাম দিকের এলিমেন্ট সবসময় ডান দিকের এলিমেন্ট থেকে ছোট বা সমান।
• দুইটি এলিমেন্ট মিলে একটি ক্লোজড ইন্টারভাল সংজ্ঞায়িত করে।
• রুট ছাড়া যেকোনো নোডের ইন্টারভাল তার প্যারেন্ট নোডের সাব-ইন্টারভাল।
• বাম দিকের এলিমেন্টগুলো মিন হিপ নির্দেশ করে।
• ডান দিকের এলিমেন্টগুলো ম্যাক্স হিপ নির্দেশ করে।