Queap
কম্পিউটার বিজ্ঞানে, একটি কুইপ একটি অগ্রাধিকার সারি তথ্য কাঠামো। তথ্য কাঠামো নির্বিচারে উপাদান সন্নিবেশ এবং মুছে ফেলার পাশাপাশি সর্বোচ্চ-অগ্রাধিকার উপাদান পুনরুদ্ধারের অনুমতি দেয়। প্রতিটি মুছে ফেলার জন্য মুছে ফেলা আইটেমের তুলনায় কাঠামোর মধ্যে দীর্ঘ সময় ধরে থাকা আইটেমের সংখ্যায় অ্যামোর্টাইজড টাইম লগারিদমিক লাগে। সন্নিবেশগুলি ক্রমাগত পরিশোধিত সময় নেয়। তথ্য কাঠামো একটি দ্বিগুণ সংযুক্ত তালিকা এবং একটি 2-4 গাছের তথ্য কাঠামো নিয়ে গঠিত, প্রতিটি তার ন্যূনতম-অগ্রাধিকার উপাদানের উপর নজর রাখার জন্য পরিবর্তিত হয়। কাঠামোর মূল কাজ হল দ্বিগুণ সংযুক্ত তালিকায় নতুন সন্নিবেশিত উপাদানগুলি রাখা, যতক্ষণ না একটি মুছে ফেলা তালিকার আইটেমগুলির মধ্যে একটি সরিয়ে ফেলবে, সেই সময়ে সেগুলি সমস্ত 2-4 গাছের মধ্যে সরানো হবে। 2-4 গাছটি তার উপাদানগুলিকে আরও প্রচলিত অগ্রাধিকার-সাজানো ক্রমের পরিবর্তে সন্নিবেশ ক্রমে সংরক্ষণ করে। তথ্য কাঠামো এবং এর নাম উভয়ই জন আইকনো এবং স্টেফান ল্যাঙ্গারম্যান দ্বারা উদ্ভাবিত হয়েছিল। বিবরণ একটি কুইপ একটি অগ্রাধিকার সারি যা ও (1) পরিশোধিত সময়ে উপাদানগুলি সন্নিবেশ করে এবং ও (লগ (কে + 2))-তে ন্যূনতম উপাদানটি সরিয়ে দেয় যদি কে আইটেমগুলি হিপে থাকে যা উপাদানটির চেয়ে বেশি সময় ধরে থাকে। কিউয়াপের একটি বৈশিষ্ট্য রয়েছে যাকে কিউইশ প্রপার্টি বলা হয়ঃ উপাদান x অনুসন্ধানের সময় হল O (lg q (x)) যেখানে q (x) হল n − 1 − w (x) এর সমান এবং w (x) হল অনুসন্ধান, সন্নিবেশ বা মুছে ফেলার মতো ক্রিয়াকলাপ দ্বারা অ্যাক্সেস করা স্বতন্ত্র আইটেমগুলির সংখ্যা। q (x) কে সংজ্ঞায়িত করা হয় যে x-এর শেষ অ্যাক্সেসের পর থেকে কতগুলি উপাদান অ্যাক্সেস করা হয়নি। প্রকৃতপক্ষে, সারি বৈশিষ্ট্যটি স্প্লে ট্রি ওয়ার্কিং সেট বৈশিষ্ট্যের পরিপূরকঃ x উপাদানটি অনুসন্ধান করার সময় হল O (lg w (x))। একটি সারি দুটি তথ্য কাঠামো দ্বারা প্রতিনিধিত্ব করা যেতে পারেঃ একটি দ্বিগুণ সংযুক্ত তালিকা এবং 2-4 গাছের একটি পরিবর্তিত সংস্করণ। দ্বিগুণভাবে সংযুক্ত তালিকা, এল, সন্নিবেশ এবং অবস্থান-মিন ক্রিয়াকলাপের একটি সিরিজের জন্য ব্যবহৃত হয়। কুইপ তালিকায় সংরক্ষিত ন্যূনতম উপাদানটির একটি পয়েন্টার রাখে। তালিকা l-এ উপাদান x যোগ করতে, উপাদান x তালিকার শেষে যোগ করা হয় এবং উপাদান x-এ একটি বিট পরিবর্তনশীল সেট করা হয়। এই অপারেশনটি নির্ধারণ করার জন্য করা হয় যে উপাদানটি তালিকায় আছে নাকি 2-4 টি গাছে। একটি 2-4 গাছ ব্যবহার করা হয় যখন একটি মুছে ফেলার অপারেশন ঘটে। যদি আইটেমটি ইতিমধ্যে ট্রি টি-তে থাকে, তবে 2-4 ট্রি মুছে ফেলার অপারেশন ব্যবহার করে আইটেমটি সরানো হয়। অন্যথায়, আইটেম x তালিকা L-এ রয়েছে (বিট পরিবর্তনশীল সেট করা আছে কিনা তা পরীক্ষা করে করা হয়)। তালিকা এল-এ সংরক্ষিত সমস্ত উপাদানগুলি তারপর 2-4 ট্রি-তে যোগ করা হয়, প্রতিটি উপাদানের বিট পরিবর্তনশীলকে শূন্যে সেট করে। তারপর টি থেকে এক্স সরানো হয়। একটি কুইপ শুধুমাত্র 2 থেকে 4 টি গাছের কাঠামোর বৈশিষ্ট্য ব্যবহার করে, কোনও সার্চ ট্রি নয়। পরিবর্তিত 2-4 টি গাছের কাঠামো নিম্নরূপ। ধরুন তালিকা এল-এ নিম্নলিখিত উপাদানগুলির সেট রয়েছেঃ যখন মুছে ফেলার প্রক্রিয়াটি আহ্বান করা হয়, তখন এল-এ সঞ্চিত উপাদানগুলির সেটটি সেই ক্রমে 2-4 টি গাছের পাতায় যোগ করা হয়, একটি অসীম কী সহ একটি ডামি পাতা দ্বারা এগিয়ে যায়। টি-এর প্রতিটি অভ্যন্তরীণ নোডের একটি পয়েন্টার থাকে, যা সাবট্রি ভি-এর ক্ষুদ্রতম আইটেমকে নির্দেশ করে। রুট থেকে পি-এর পথে প্রতিটি অভ্যন্তরীণ নোডের একটি পয়েন্টার থাকে, যা সবচেয়ে ছোট কী-কে নির্দেশ করে। পি পথের প্রতিটি অভ্যন্তরীণ নোডের নির্দেশকগুলি উপেক্ষা করা হয়। সারিটির একটি নির্দেশক রয়েছে, যা টি-র ক্ষুদ্রতম উপাদানটিকে নির্দেশ করে। সারিগুলির প্রয়োগের মধ্যে রয়েছে উচ্চ অগ্রাধিকার ইভেন্টগুলির একটি অনন্য সেট এবং প্রক্রিয়াকরণের জন্য সর্বোচ্চ অগ্রাধিকার ইভেন্টের নিষ্কাশন। মিনএলকে একটি নির্দেশক হিসাবে ধরা যাক যা দ্বিগুণ সংযুক্ত তালিকা এল-এর সর্বনিম্ন উপাদানকে নির্দেশ করে, 2 থেকে 4 টি ট্রি-তে সঞ্চিত ন্যূনতম উপাদান হতে হবে, টি, কে টি-তে সঞ্চিত উপাদানের সংখ্যা হতে হবে এবং এন কোয়াপ কিউ-তে সঞ্চিত উপাদানগুলির মোট সংখ্যা হতে হবে। ক্রিয়াকলাপগুলি নিম্নরূপঃ নতুন (প্রশ্ন): একটি নতুন খালি সারি শুরু করে। একটি খালি দ্বিগুণ লিঙ্কযুক্ত তালিকা এল এবং 2-4 টি ট্রি শুরু করুন। কে এবং এন শূন্য সেট করুন। সন্নিবেশ করান (প্রশ্ন, x): সারিতে x উপাদান যোগ করুন। তালিকা এল-এ x উপাদানটি সন্নিবেশ করান। উপাদানটি এল-এর তালিকায় রয়েছে তা দেখানোর জন্য উপাদান এক্স-এ বিটটি একটিতে সেট করুন। যদি x তালিকার ক্ষুদ্রতম উপাদান হয় তবে মিনএল পয়েন্টারটি আপডেট করুন। 1 দ্বারা এন বৃদ্ধি। ন্যূনতম (প্রশ্ন): কুইপ কিউ থেকে ক্ষুদ্রতম উপাদানটির একটি পয়েন্টার পুনরুদ্ধার করুন। যদি কী (মিনিএল) <কী () হয়, তাহলে মিনিএল ফেরত দিন। অন্যথায় ফিরে আসুন। মুছে ফেলুন (কিউ, এক্স): কোয়াপ কিউ থেকে এক্স উপাদানটি সরিয়ে ফেলুন। যদি x উপাদানটির বিট একটিতে সেট করা থাকে, তবে উপাদানটি L তালিকায় সংরক্ষণ করা হয়। L থেকে T পর্যন্ত সমস্ত উপাদান যোগ করুন, প্রতিটি উপাদানের বিটকে শূন্যে সেট করুন। প্রতিটি উপাদান 2-4 গাছের সন্নিবেশ ক্রিয়াকলাপ ব্যবহার করে টি-এর ডান দিকের সবচেয়ে বেশি সন্তানের পিতামাতার সাথে যুক্ত করা হয়। এল খালি হয়ে যায়। সমস্ত নোডের জন্য পয়েন্টারগুলি আপডেট করুন যার সন্তানরা নতুন/পরিবর্তিত, এবং পরবর্তী পিতামাতার সাথে প্রক্রিয়াটি পুনরাবৃত্তি করুন যতক্ষণ না পিতামাতা মূলের সমান হয়। মূল থেকে নোড পর্যন্ত হাঁটুন এবং মানগুলি আপডেট করুন। k কে n এর সমান নির্ধারণ করুন। যদি x উপাদানটির বিট শূন্যে সেট করা থাকে, x হল T এর একটি পাতা। 2-4 ট্রি মুছে ফেলার ক্রিয়া ব্যবহার করে x মুছে ফেলুন। নোড এক্স থেকে শুরু করে, টি থেকে নোড পর্যন্ত হাঁটুন, আপডেট করুন এবং পয়েন্টার দিন। n এবং k কে 1 দ্বারা হ্রাস করুন। ডিলিটমিন (কিউ): কুইপ কিউ থেকে ক্ষুদ্রতম উপাদানটি মুছে ফেলুন এবং ফেরত দিন। ন্যূনতম (কিউ) অপারেশন আহ্বান করুন। অপারেশন মিনিট ফেরত দেয়। মুছে ফেলুন (প্রশ্ন, মিনিট) অপারেশনটি আহ্বান করুন। মিনিট ফেরত দিন। ক্লিনআপ (প্রশ্ন): তালিকা এল এবং ট্রি টি-র সমস্ত উপাদান মুছে ফেলুন। তালিকা এল-এর প্রথম উপাদান থেকে শুরু করে, প্রতিটি নোড মুছে দিয়ে তালিকাটি অতিক্রম করুন। টি গাছের মূল থেকে শুরু করে, পোস্ট-অর্ডার ট্র্যাভার্সাল অ্যালগরিদম ব্যবহার করে গাছের প্রতিটি নোড মুছে ফেলুন। বিশ্লেষণ ঋণ পরিশোধিত বিশ্লেষণ ব্যবহার করে চলমান সময় বিশ্লেষণ করা হয়। কুইপ কিউ-এর সম্ভাব্য ফাংশন কোথায় হবে। সন্নিবেশ করান (প্রশ্ন, x): অপারেশনের খরচ হল ও (1)। তালিকা এল-এর আকার এক গুণ বৃদ্ধি পায়, সম্ভাব্যতা কিছু ধ্রুবক বৃদ্ধি পায় সি। ন্যূনতম (কিউ): অপারেশনটি ডেটা কাঠামোকে পরিবর্তন করে না তাই ঋণ পরিশোধের খরচ তার প্রকৃত খরচ, ও (1)-এর সমান। মুছে ফেলুন (প্রশ্ন, x): দুটি কেস রয়েছে। কেস 1 যদি x গাছ টি-তে থাকে, তাহলে ঋণ পরিশোধের খরচ পরিবর্তিত হয় না। মুছে ফেলার প্রক্রিয়াটি হল ও (1) আমোর্টাইজড 2-4 গাছ। যেহেতু এক্স গাছ থেকে সরানো হয়েছে, এবং পয়েন্টারগুলি আপডেট করার প্রয়োজন হতে পারে। সর্বাধিক, আপডেট থাকবে। দ্বিতীয় ক্ষেত্রে, যদি x তালিকা L-এ থাকে, তাহলে L-এর সমস্ত উপাদান T-তে ঢোকানো হয়। এবং পয়েন্টারগুলি সন্নিবেশ এবং আপডেট করার পরে, ব্যয় করা মোট সময় দ্বারা সীমাবদ্ধ। দ্বিতীয় ক্রিয়াটি হল T থেকে x মুছে ফেলা, এবং x থেকে x-এর পথে হাঁটা, সংশোধন এবং মান করা। সর্বাধিক সময় ব্যয় করা হয়। যদি হয়, তাহলে ঋণ পরিশোধের খরচ হবে। মুছে ফেলুন (কিউ, এক্স): ন্যূনতম (কিউ) এবং মুছে ফেলুন (কিউ, এক্স) এর পরিশোধিত ব্যয়ের সংযোজন, যা হল। কোডের উদাহরণ একটি কুইপের একটি ছোট জাভা বাস্তবায়নঃ পাবলিক ক্লাস কুইপ {পাবলিক ইন্ট এন, কে; পাবলিক লিস্ট <এলিমেন্ট> এল;// এলিমেন্ট হল একটি জেনেরিক ডেটা টাইপ। পাবলিক কুইপট্রি টি;// একটি 2-4 ট্রি, কুইপ উদ্দেশ্যে পাবলিক এলিমেন্ট মিনিএল-এর জন্য পরিবর্তিত; প্রাইভেট কুইপ () {এন = 0; কে = 0; এল = নতুন লিঙ্কড লিস্ট <এলিমেন্ট> (); টি = নতুন কুইপট্রি ();} পাবলিক স্ট্যাটিক কুইপ নিউ () {রিটার্ন নিউ কুইপ ();} পাবলিক স্ট্যাটিক অকার্যকর সন্নিবেশ (কুইপ কিউ, এলিমেন্ট এক্স) {যদি (কিউ. এন = = 0) Q.minL = এক্স; Q.l.add (এক্স); x.inList = সত্য; যদি (x.compareTo (Q.minL) <0) Q.minL = এক্স;} পাবলিক স্ট্যাটিক এলিমেন্ট ন্যূনতম (কুইপ কিউ) { যদি (Q.minL.compareTo (Q.t.x0.cv. কী) <0) ফেরত দেয় Q.minL; ফেরত দেয় Q.t.x0.cv. কী;} পাবলিক স্ট্যাটিক অকার্যকর মুছে ফেলুন (কুইপ কিউ, কুইপনোড এক্স) {Q.t.deleteLeaf (এক্স);---কিউ. এন;-- কিউ. কে;} পাবলিক স্ট্যাটিক অকার্যকর মুছে ফেলুন (কুইপ কিউ, এলিমেন্ট এক্স) {কুইপনোড এন; যদি (x.inList) {// তালিকায় সমস্ত উপাদানের তালিকা মিথ্যা এন = Q.t.insertList (কিউ. এল, এক্স); কিউ. কে = কিউ. এন; মুছে ফেলুন (কিউ, এন); অন্যথায় যদি (এন = Q.t.x0.cv).