Kinetic heap
একটি কাইনেটিক হিপ হল একটি কাইনেটিক ডেটা স্ট্রাকচার, যা একটি হিপের কাইনেটাইজেশন দ্বারা প্রাপ্ত হয়। এটি এমন উপাদানগুলি (অগ্রাধিকারের সাথে সম্পর্কিত কীগুলি) সংরক্ষণ করার জন্য ডিজাইন করা হয়েছে যেখানে সময়ের একটি অবিচ্ছিন্ন ফাংশন হিসাবে অগ্রাধিকার পরিবর্তন হচ্ছে। এক ধরনের গতিজ অগ্রাধিকার সারি হিসাবে, এটি এতে সংরক্ষিত সর্বাধিক অগ্রাধিকার উপাদান বজায় রাখে। কাইনেটিক হিপ ডেটা স্ট্রাকচার উপাদানগুলিকে একটি গাছ হিসাবে সংরক্ষণ করে কাজ করে যা নিম্নলিখিত হিপ বৈশিষ্ট্যকে সন্তুষ্ট করে যদি এটি একটি চাইল্ড নোড হয়, তবে উপাদানটির অগ্রাধিকার অবশ্যই উপাদানটির অগ্রাধিকারের চেয়ে বেশি হতে হবে। এই গাদা সম্পত্তিটি প্রতিটি প্রান্ত বরাবর শংসাপত্র ব্যবহার করে প্রয়োগ করা হয়, তাই অন্যান্য গতিজ তথ্য কাঠামোর মতো, একটি গতিজ গাদা শংসাপত্র ব্যর্থতার সময় বজায় রাখার জন্য একটি অগ্রাধিকার সারি (ইভেন্ট সারি) ধারণ করে। বাস্তবায়ন এবং ক্রিয়াকলাপ একটি নিয়মিত স্তূপকে প্রতিটি জোড়া নোডের জন্য একটি শংসাপত্র [] দিয়ে বৃদ্ধি করে গতিময় করা যেতে পারে, যেমন একটি চাইল্ড নোড। যদি কোনও নোডে সঞ্চিত মানটি সময়ের একটি ফাংশন হয়, তবে এই শংসাপত্রটি কেবল তখনই বৈধ। সুতরাং, এই শংসাপত্রের ব্যর্থতা অবশ্যই ইভেন্টের সারিতে এমন একটি সময়ে নির্ধারণ করা উচিত যাতে। সমস্ত শংসাপত্র ব্যর্থতা "ইভেন্ট সারি"-তে নির্ধারিত হয়, যা একটি দক্ষ অগ্রাধিকার সারি বলে মনে করা হয় যার ক্রিয়াকলাপে সময় লাগে। শংসাপত্রের ব্যর্থতা মোকাবেলা যখন একটি শংসাপত্র [] ব্যর্থ হয়, তখন তথ্য কাঠামোকে অবশ্যই অদলবদল করতে হবে এবং স্তূপের মধ্যে রাখতে হবে এবং প্রতিটি শংসাপত্রের মধ্যে উপস্থিত শংসাপত্রগুলি আপডেট করতে হবে। উদাহরণস্বরূপ, যদি (চাইল্ড নোড এবং) একটি চাইল্ড নোড (চাইল্ড নোড এবং প্যারেন্ট নোড সহ) হয়, এবং শংসাপত্রটি ব্যর্থ হয়, তবে ডেটা স্ট্রাকচারটি অবশ্যই অদলবদল করতে হবে এবং তারপরে পুরানো শংসাপত্রগুলি (এবং সংশ্লিষ্ট নির্ধারিত ইভেন্টগুলি) [], [], [], [], [], নতুন শংসাপত্র [], [], [], [] এবং [] দিয়ে প্রতিস্থাপন করতে হবে। সুতরাং, ঘটনাগুলির অ-অবনতি ধরে নিয়ে (একই সময়ে কোনও দুটি ঘটনা ঘটে না), কেবলমাত্র একটি ধ্রুবক সংখ্যক ইভেন্টকে ডি-শিডিউল করা এবং সবচেয়ে খারাপ ক্ষেত্রেও পুনরায় শিডিউল করা প্রয়োজন। ক্রিয়াকলাপ একটি কাইনেটিক হিপ নিম্নলিখিত ক্রিয়াকলাপগুলিকে সমর্থন করেঃ একটি খালি কাইনেটিক হিপ (বা ফাইন্ড-মিন) তৈরি করুনঃ বর্তমান ভার্চুয়াল সময়ে হিপে সঞ্চিত (বা a এর জন্য) মানটি ফেরত দিন। : বর্তমান ভার্চ্যুয়াল সময়ে কাইনেটিক হিপে একটি কী সন্নিবেশ করান, যার মান সময়ের অবিচ্ছিন্ন ফাংশন হিসাবে পরিবর্তিত হয়। সময়মতো একটি স্বাভাবিক স্তূপের মতো সন্নিবেশ করা হয়, তবে ফলস্বরূপ শংসাপত্রগুলি পরিবর্তন করার প্রয়োজন হতে পারে, তাই শংসাপত্র ব্যর্থতার পুনঃনির্ধারণের জন্য মোট সময় বর্তমান ভার্চুয়াল সময়ে একটি কী মুছে ফেলা হয়। মুছে ফেলা স্বাভাবিক সময়ের মতো করা হয়, তবে ফলস্বরূপ শংসাপত্রগুলি পরিবর্তন করতে হতে পারে, তাই শংসাপত্র ব্যর্থতার পুনঃনির্ধারণের জন্য মোট সময় হয়। পারফরম্যান্স কাইনেটিক হিপগুলি ব্যাস এট আল দ্বারা সংজ্ঞায়িত কাইনেটিক ডেটা স্ট্রাকচার মানের চারটি মেট্রিক (প্রতিক্রিয়াশীলতা, স্থানীয়তা, কম্প্যাক্টনেস এবং দক্ষতা) অনুযায়ী ভাল পারফর্ম করে। প্রথম তিনটি গুণাবলীর বিশ্লেষণ সহজবোধ্যঃ প্রতিক্রিয়াশীলঃ একটি গতিশীল স্তূপ প্রতিক্রিয়াশীল, কারণ প্রতিটি শংসাপত্রের ব্যর্থতার কারণে সংশ্লিষ্ট কীগুলি অদলবদল করা হয় এবং সবচেয়ে খারাপ ক্ষেত্রে মাত্র কয়েকটি শংসাপত্র প্রতিস্থাপিত হয়। স্থানীয়তাঃ প্রতিটি নোড তার মূল নোড এবং দুটি চাইল্ড নোড (যদি থাকে) সহ একটি শংসাপত্রে উপস্থিত থাকে, যার অর্থ হল যে প্রতিটি নোড সবচেয়ে খারাপ ক্ষেত্রে মোট তিনটি নির্ধারিত ইভেন্টে জড়িত থাকতে পারে, এইভাবে গতিময় স্তূপগুলি স্থানীয়। কম্প্যাক্টনেসঃ স্তূপের প্রতিটি প্রান্ত ঠিক একটি নির্ধারিত ইভেন্টের সাথে মিলে যায়, তাই নির্ধারিত ইভেন্টের সংখ্যা ঠিক যেখানে গতিজ স্তূপের নোডের সংখ্যা। সুতরাং, কাইনেটিক হিপগুলি কম্প্যাক্ট। দক্ষতার বিশ্লেষণ সাধারণ ক্ষেত্রে একটি গতিজ স্তূপের দক্ষতা মূলত অজানা। যাইহোক, অগ্রাধিকারগুলির অ্যাফিন গতির বিশেষ ক্ষেত্রে, গতিজ স্তূপগুলি খুব কার্যকর বলে জানা যায়। অ্যাফিন গতি, কোনও সন্নিবেশ বা মুছে ফেলা নয় এই বিশেষ ক্ষেত্রে, একটি গতিজ স্তূপ দ্বারা প্রক্রিয়াজাত ইভেন্টের সর্বাধিক সংখ্যাটি স্তূপের গাছের কাঠামোর ক্ষণস্থায়ী বন্ধের ঠিক প্রান্তের সংখ্যা হিসাবে দেখানো যেতে পারে, যা উচ্চতার গাছের জন্য। সন্নিবেশ এবং মুছে ফেলার সাথে অ্যাফিন গতি যদি খালি শুরু হওয়া একটি গতিজ স্তূপের উপর সন্নিবেশ এবং মুছে ফেলা হয়, তবে প্রক্রিয়াজাত ইভেন্টের সর্বাধিক সংখ্যা হল তবে, এই সীমাটি আঁটসাঁট বলে মনে করা হয় না এবং একমাত্র পরিচিত নিম্ন সীমা হল। বৈচিত্র্য এই নিবন্ধটি উপরে বর্ণিত "সহজ" গতিজ স্তূপের সাথে সম্পর্কিত, তবে অন্যান্য রূপগুলি বিশেষ প্রয়োগের জন্য তৈরি করা হয়েছে, যেমনঃ ফিবোনাচি গতিজ স্তূপ ক্রমবর্ধমান গতিজ স্তূপ অন্যান্য স্তূপের মতো গতিজ অগ্রাধিকার সারিগুলি হলঃ গতিজ হিটার গতিজ হ্যাঙ্গার রেফারেন্স গতিজ তথ্য কাঠামো স্তূপ (তথ্য কাঠামো)