ডুয়াল হিপ
সিঙ্গেল-এন্ডেড প্রায়োরিটি কিউ (PQ) ডেটা স্ট্রাকচার থেকে দক্ষ DEPQ (ডাবল এন্ডেড প্রায়োরিটি কিউ) ডেটা স্ট্রাকচারে পৌঁছানোর সাধারণ পদ্ধতির অস্তিত্ব যা রিমুভ(aNode) অপারেশনের একটি দক্ষ বাস্তবায়ন প্রদান করে (এই অপারেশনটি থেকে নোড aNode বাদ দেয় PQ)। এই পদ্ধতিগুলির মধ্যে সবচেয়ে সহজ, ডুয়াল স্ট্রাকচার পদ্ধতি, ন্যূনতম PQ এবং একই উপাদান সমন্বিত সর্বাধিক PQ-এর নোডগুলির মধ্যে চিঠিপত্রের পয়েন্টারগুলির সাথে যুক্ত সমস্ত DEPQ উপাদানগুলির একটি ন্যূনতম PQ এবং সর্বাধিক PQ উভয়েরই ট্র্যাক রাখে৷
চিত্র A 7, 8, 3, 6, 5 উপাদানগুলির জন্য একটি দ্বৈত হিপ গঠন প্রদর্শন করে। চিঠিপত্রের পয়েন্টারগুলি লাল তীর হিসাবে প্রদর্শিত হয়।
চিত্র A:ডুয়েল হিপ
যদিও চিত্রটি ন্যূনতম এবং সর্বোচ্চ উভয় স্তূপে সংরক্ষিত প্রতিটি উপাদান প্রদর্শন করে, তবে প্রতিটি উপাদানকে দুটি স্তূপের মধ্যে একটিতে সংরক্ষণ করতে হবে৷
isEmpty এবং আকারের ক্রিয়াকলাপগুলি একটি পরিবর্তনশীল আকার প্রয়োগ করে প্রয়োগ করা হয় যা DEPQ-এর উপাদানগুলির সংখ্যার উপর নজর রাখে। সর্বনিম্ন উপাদানটি মিন হিপের মূলে অবস্থিত এবং সর্বাধিক উপাদানটি সর্বাধিক স্তূপের মূলে অবস্থিত। একটি উপাদান A সন্নিবেশ করার জন্য, আমরা ন্যূনতম এবং সর্বোচ্চ উভয় স্তূপে A সন্নিবেশ করি এবং তারপরে ন্যূনতম এবং সর্বোচ্চ স্তূপের মধ্যে A এর অবস্থানগুলির মধ্যে চিঠিপত্র পয়েন্টার সেট আপ করি। ন্যূনতম উপাদানটি নির্মূল করার জন্য, আমরা মিন হিপ থেকে একটি রিমুভমিন করি এবং একটি রিমুভ(aNode), যেখানে aNode হল সর্বাধিক হিপ থেকে সরানো উপাদানটির জন্য সংশ্লিষ্ট নোড। সর্বাধিক উপাদান একটি সাদৃশ্য উপায়ে নির্মূল করা হয়।
মোট এবং পাতার চিঠিপত্র
মোট এবং পাতার চিঠিপত্র আরও পরিশীলিত চিঠিপত্রের কৌশল। এই উভয় কৌশলেই, অর্ধেক উপাদান ন্যূনতম PQ এবং বাকি অর্ধেক সর্বাধিক PQ-তে অবস্থিত। যখন উপাদানের সংখ্যা বিজোড় হয়, তখন একটি উপাদান একটি বাফারে সংরক্ষণ করা হয়। এই বাফার করা উপাদান PQ-এর সদস্য নয়। মোট চিঠিপত্রের কৌশলে, ন্যূনতম PQ-এর প্রতিটি উপাদান x সর্বাধিক PQ-এর একটি স্বতন্ত্র উপাদান y-এর সাথে যুক্ত হয়। (x, y) উপাদানগুলির একটি অনুরূপ জোড়া যেমন অগ্রাধিকার(x) <=অগ্রাধিকার(y)।
চিত্র B 11টি উপাদান 3, 4, 5, 5, 6, 6, 7, 8, 9, 10, 11-এর জন্য মোট চিঠিপত্রের স্তূপ প্রদর্শন করে। উপাদান 10টি বাফারে রয়েছে। অনুরূপ জোড়া লাল তীর দ্বারা প্রদর্শিত হয়।
চিত্র B:মোট চিঠিপত্রের স্তূপ
পাতার চিঠিপত্রের কৌশলে, ন্যূনতম এবং সর্বোচ্চ PQ-এর প্রতিটি পাতার উপাদান একটি সংশ্লিষ্ট জোড়ার অংশ হতে হবে। ননলিফ উপাদানগুলির কোন অনুরূপ জোড়ায় থাকার প্রয়োজন নেই। চিত্র সি একটি পাতার চিঠিপত্রের স্তূপ প্রদর্শন করে।
চিত্র সি:একটি পাতার চিঠিপত্রের স্তূপ
মোট এবং পাতার চিঠিপত্রের কাঠামো দ্বৈত কাঠামোর তুলনায় কম স্থান প্রয়োজন। যাইহোক, মোট এবং পাতার চিঠিপত্রের কাঠামোর জন্য DEPQ অ্যালগরিদমগুলি দ্বৈত কাঠামোর তুলনায় আরও জটিল। তিনটি চিঠিপত্রের কৌশলগুলির মধ্যে, পাতার চিঠিপত্র হল দ্রুততম DEPQ চিঠিপত্রের কাঠামো৷
বর্ণিত চিঠিপত্রের যেকোন কৌশল প্রয়োগ করে, আমরা স্তূপ, উচ্চতা পক্ষপাতী বামপন্থী গাছ এবং জোড়ার স্তূপ থেকে DEPQ কাঠামোতে পৌঁছাতে পারি। এই DEQP স্ট্রাকচারে, অপারেশন পুট(x), রিমুভমিন(), এবং রিমুভম্যাক্স() O(লগ n) সময় খরচ করে (n হল DEPQ-এ উপাদানের সংখ্যা, গাদা জোড়ার জন্য, এটি একটি পরিমার্জিত জটিলতা), এবং অবশিষ্ট DEPQ অপারেশনগুলি O(1) সময় ব্যয় করে।
