ডুয়াল হিপ
সাধারণ পদ্ধতিগুলোর অস্তিত্ব রয়েছে যারা দক্ষ DEPQ (ডাবল-এন্ডেড প্রায়োরিটি কিউ) ডেটা স্ট্রাকচার তৈরি করে সিঙ্গল-এন্ডেড প্রায়োরিটি কিউ (PQ) ডেটা স্ট্রাকচার থেকে যেগুলো remove(aNode) অপারেশনের দক্ষ ইমপ্লিমেন্টেশনও প্রদান করে (এই অপারেশন PQ থেকে aNode নোডকে সরিয়ে দেয়)। এই পদ্ধতিগুলোর মধ্যে সবচেয়ে সহজ হলো ডুয়াল স্ট্রাকচার মেথড, যা একটি মিন PQ এবং একটি ম্যাক্স PQ রক্ষা করে DEPQ-এর সকল এলিমেন্টের জন্য এবং করেসপন্ডেন্স পয়েন্টার ব্যবহার করে মিন PQ এবং ম্যাক্স PQ-এর নোডগুলোর মধ্যে যেসব একই এলিমেন্ট নিয়ে গঠিত।
চিত্র A এলিমেন্ট ৭, ৮, ৩, ৬, ৫ এর জন্য একটি ডুয়াল হিপ স্ট্রাকচার প্রদর্শন করে। করেসপন্ডেন্স পয়েন্টার লাল তীর হিসেবে দেখানো হয়েছে।
চিত্র A: ডুয়াল হিপ
যদিও চিত্রে প্রতিটি এলিমেন্ট মিন এবং ম্যাক্স হিপ দুটোতেই সংরক্ষিত দেখানো হয়েছে, আসলে প্রতিটি এলিমেন্ট দুটি হিপের যেকোনো একটি-তে সংরক্ষণ করা আবশ্যক।
isEmpty এবং size অপারেশন একটি size ভেরিয়েবল ব্যবহার করে ইমপ্লিমেন্ট করা হয় যা DEPQ-তে এলিমেন্টের সংখ্যা ট্র্যাক করে। মিনিমাম এলিমেন্ট মিন হিপের রুটে থাকে এবং ম্যাক্সিমাম এলিমেন্ট ম্যাক্স হিপের রুটে থাকে। একটি এলিমেন্ট A ইনসার্ট করতে, আমরা A কে মিন এবং ম্যাক্স হিপ দুটোতেই ইনসার্ট করি এবং তারপর A-এর মিন ও ম্যাক্স হিপে লোকেশনের মধ্যে করেসপন্ডেন্স পয়েন্টার সেট আপ করি। মিনিমাম এলিমেন্ট সরাতে, আমরা মিন হিপ থেকে removeMin এবং ম্যাক্স হিপ থেকে remove(aNode) করেন, যেখানে aNode হলো সরানো এলিমেন্টের জন্য করেসপন্ডিং নোড। ম্যাক্সিমাম এলিমেন্টও অনুরূপভাবে সরানো হয়।
টোটাল এবং লিফ করেসপন্ডেন্স
টোটাল এবং লিফ করেসপন্ডেন্স আরও উন্নত করেসপন্ডেন্স কৌশল। এই দুটি কৌশলে, অর্ধেক এলিমেন্ট মিন PQ-তে এবং বাকি অর্ধেক ম্যাক্স PQ-তে থাকে। এলিমেন্টের সংখ্যা বিজোড় হলে, একটি এলিমেন্ট বাফারে সংরক্ষিত হয়। এই বাফার্ড এলিমেন্ট কোনো PQ-এর সদস্য নয়। টোটাল করেসপন্ডেন্স টেকনিকে, মিন PQ-তেক প্রতিটি এলিমেন্ট x ম্যাক্স PQ-র একটি স্বতন্ত্র এলিমেন্ট y সাথে জোড়া বাঁধা হয়। (x, y) একটি করেসপন্ডিং পেয়ার যাতে priority(x) ≤ priority(y)।
চিত্র B ১১টি এলিমেন্ট ৩, ৪, ৫, ৫, ৬, ৬, ৭, ৮, ৯, ১০, ১১ এর জন্য একটি টোটাল করেসপন্ডেন্স হিপ প্রদর্শন করে। এলিমেন্ট ১০ বাফারে রয়েছে। করেসপন্ডিং পেয়ারগুলি লাল তীর চিহ্নিত করা হয়েছে।
চিত্র B: টোটাল করেসপন্ডেন্স হিপ
লিফ করেসপন্ডেন্স টেকনিকে, মিন এবং ম্যাক্স PQ-র প্রতিটি লিফ এলিমেন্ট একটি করেসপন্ডিং পেয়ারের অংশ হতে হবে। নন-লিফ এলিমেন্টগুলোর কোনো করেসপন্ডিং পেয়ারে থাকা আবশ্যক নয়। চিত্র C একটি লিফ করেসপন্ডেন্স হিপ প্রদর্শন করে।
চিত্র C: একটি লিফ করেসপন্ডেন্স হিপ
টোটাল এবং লিফ করেসপন্ডেন্স স্ট্রাকচার ডুয়াল স্ট্রাকচারের চেয়ে কম স্পেস দরকার করে। তবে, টোটাল এবং লিফ করেসপন্ডেন্স স্ট্রাকচারের DEPQ অ্যালগরিদম ডুয়াল স্ট্রাকচারের চেয়ে আরও জটিল। তিনটি করেসপন্ডেন্স টেকনিকের মধ্যে, লিফ করেসপন্ডেন্স দ্রুততম DEPQ করেসপন্ডেন্স স্ট্রাকচার।
বর্ণিত যেকোনো করেসপন্ডেন্স টেকনিক ইমপ্লিমেন্ট করে, আমরা হিপ, হাইট-বায়াসড লেফটিস্ট ট্রি, এবং পেয়ারিং হিপ থেকে DEPQ স্ট্রাকচার পেতে পারি। এই DEPQ স্ট্রাকচারগুলিতে, put(x), removeMin(), এবং removeMax() অপারেশন O(log n) টাইম নেয় (n হলো DEPQ-তে এলিমেন্টের সংখ্যা, পেয়ারিং হিপের জন্য এটি অ্যামোর্টাইজড কমপ্লেক্সিটি), এবং বাকি DEPQ অপারেশন O(1) টাইম নেয়।
