Kinetic heap
حرکی ڈھیر ایک حرکی ڈیٹا ڈھانچہ ہے، جو ڈھیر کی حرکیات سے حاصل ہوتا ہے۔ یہ عناصر (ترجیحات سے وابستہ چابیاں) کو ذخیرہ کرنے کے لیے ڈیزائن کیا گیا ہے جہاں ترجیح وقت کے مسلسل کام کے طور پر تبدیل ہو رہی ہے۔ حرکی ترجیحی قطار کی ایک قسم کے طور پر، یہ اس میں محفوظ کردہ زیادہ سے زیادہ ترجیحی عنصر کو برقرار رکھتی ہے۔ حرکی ڈھیر ڈیٹا ڈھانچہ عناصر کو ایک درخت کے طور پر ذخیرہ کرکے کام کرتا ہے جو مندرجہ ذیل ڈھیر کی خاصیت کو مطمئن کرتا ہے اگر چائلڈ نوڈ ہے، تو اس میں عنصر کی ترجیح عنصر کی ترجیح سے زیادہ ہونی چاہیے۔ اس ڈھیر کی خاصیت کو ہر کنارے کے ساتھ سرٹیفکیٹ کا استعمال کرتے ہوئے نافذ کیا جاتا ہے، لہذا دیگر حرکی ڈیٹا ڈھانچوں کی طرح، ایک حرکی ڈھیر میں بھی سرٹیفکیٹ کی ناکامی کے اوقات کو برقرار رکھنے کے لیے ترجیحی قطار (ایونٹ قطار) ہوتی ہے۔ نفاذ اور کارروائیاں ایک باقاعدہ ڈھیر کو نوڈس کے ہر جوڑے کے لیے ایک سرٹیفکیٹ [] کے ساتھ بڑھا کر متحرک کیا جا سکتا ہے، جیسے کہ ایک چائلڈ نوڈ۔ اگر نوڈ پر ذخیرہ شدہ ویلیو وقت کا فنکشن ہے، تو یہ سرٹیفکیٹ صرف اس وقت تک درست ہے۔ اس طرح، اس سرٹیفکیٹ کی ناکامی کو ایونٹ کی قطار میں اس طرح شیڈول کیا جانا چاہیے کہ۔ تمام سرٹیفکیٹ کی ناکامیاں "ایونٹ قطار" پر شیڈول کی جاتی ہیں، جسے ایک موثر ترجیحی قطار سمجھا جاتا ہے جس کی کارروائیوں میں وقت لگتا ہے۔ سرٹیفکیٹ کی ناکامیوں سے نمٹنا جب کوئی سرٹیفکیٹ [] ناکام ہوجاتا ہے، تو ڈیٹا ڈھانچے کو ڈھیر میں تبدیل ہونا چاہیے، اور ان سرٹیفکیٹس کو اپ ڈیٹ کرنا چاہیے جن میں ان میں سے ہر ایک موجود تھا۔ مثال کے طور پر، اگر (چائلڈ نوڈس اور کے ساتھ) چائلڈ نوڈس (چائلڈ نوڈس اور پیرنٹ نوڈس کے ساتھ) تھا، اور سرٹیفکیٹ [] ناکام ہوجاتا ہے، تو ڈیٹا ڈھانچہ کو تبدیل کرنا ہوگا اور پھر پرانے سرٹیفکیٹ (اور متعلقہ شیڈول شدہ واقعات) []، []، []، []، []، نئے سرٹیفکیٹ []، []، []، [] اور [] کے ساتھ تبدیل کرنا ہوگا۔ اس طرح، واقعات کی غیر انحطاط کو فرض کرتے ہوئے (ایک ہی وقت میں کوئی دو واقعات نہیں ہوتے ہیں)، صرف واقعات کی مستقل تعداد کو ڈی شیڈول کرنے اور بدترین صورت حال میں بھی دوبارہ شیڈول کرنے کی ضرورت ہے۔ حرکتیں ایک حرکی ڈھیر مندرجہ ذیل کارروائیوں کی حمایت کرتا ہے:: ایک خالی حرکی ڈھیر بنائیں (یا کم سے کم تلاش کریں): موجودہ ورچوئل وقت پر ڈھیر میں ذخیرہ شدہ (یا a کے لیے) قیمت واپس کریں۔ : موجودہ ورچوئل وقت پر حرکی ڈھیر میں ایک کلید داخل کریں، جس کی قیمت وقت کی مسلسل تقریب کے طور پر تبدیل ہوتی ہے۔ اندراج وقت کے ساتھ عام ڈھیر کی طرح کیا جاتا ہے، لیکن اس کے نتیجے میں سرٹیفکیٹ کو تبدیل کرنے کی ضرورت پڑ سکتی ہے، لہذا سرٹیفکیٹ کی ناکامیوں کو دوبارہ ترتیب دینے کا کل وقت موجودہ ورچوئل وقت پر کلید کو حذف کرنا ہے۔ حذف کرنا وقت کے ساتھ عام ڈھیر کی طرح کیا جاتا ہے، لیکن اس کے نتیجے میں سرٹیفکیٹ کو تبدیل کرنے کی ضرورت پڑ سکتی ہے، لہذا سرٹیفکیٹ کی ناکامی کو دوبارہ ترتیب دینے کا کل وقت ہے۔ کارکردگی حرکی ڈھیر باسچ اور دیگر کے ذریعہ بیان کردہ حرکی ڈیٹا ڈھانچے کے معیار کے چار میٹرکس (ردعمل، لوکیٹی، کمپیکٹنیس اور ایفیشنسی) کے مطابق اچھی کارکردگی کا مظاہرہ کرتے ہیں۔ پہلی تین خصوصیات کا تجزیہ سیدھا ہے: ردعمل: ایک حرکی ڈھیر ذمہ دار ہوتا ہے، کیونکہ ہر سرٹیفکیٹ کی ناکامی متعلقہ چابیاں بدلنے کا سبب بنتی ہے اور بدترین صورت میں صرف چند سرٹیفکیٹ تبدیل کیے جاتے ہیں۔ لوکلٹی: ہر نوڈ اپنے پیرنٹ نوڈ اور دو چائلڈ نوڈس (اگر موجود ہو) کے ساتھ ایک سرٹیفکیٹ میں موجود ہوتا ہے، جس کا مطلب ہے کہ ہر نوڈ بدترین صورت میں کل تین شیڈول ایونٹس میں شامل ہو سکتا ہے، اس طرح حرکی ڈھیر مقامی ہوتے ہیں۔ کمپیکٹنیس: ڈھیر میں ہر کنارے بالکل ایک طے شدہ واقعہ سے مطابقت رکھتا ہے، لہذا طے شدہ واقعات کی تعداد بالکل وہی ہے جہاں حرکی ڈھیر میں نوڈس کی تعداد ہے۔ اس طرح، حرکی ڈھیر کمپیکٹ ہوتے ہیں۔ کارکردگی کا تجزیہ عام صورت میں حرکی ڈھیر کی کارکردگی بڑی حد تک نامعلوم ہے۔ تاہم، ترجیحات کی افائن حرکت کے خاص معاملے میں، حرکی ڈھیر بہت موثر ہونے کے لیے جانے جاتے ہیں۔ افائن حرکت، کوئی اندراج یا حذف نہیں اس خاص معاملے میں، حرکی ڈھیر کے ذریعے عمل کیے جانے والے واقعات کی زیادہ سے زیادہ تعداد کو ڈھیر کے درخت کے ڈھانچے کی عارضی بندش میں بالکل کناروں کی تعداد کے طور پر دکھایا جا سکتا ہے، جو اونچائی والے درخت کے لیے ہے۔ اگر کسی حرکی ڈھیر پر اندراج اور حذفیاں کی جاتی ہیں جو خالی شروع ہوتا ہے، تو کارروائی شدہ واقعات کی زیادہ سے زیادہ تعداد ہوتی ہے۔ تاہم، خیال کیا جاتا ہے کہ یہ باؤنڈ تنگ نہیں ہے، اور صرف نچلی باؤنڈ معلوم ہے۔ متغیرات یہ مضمون "سادہ" حرکی ڈھیروں سے متعلق ہے جیسا کہ اوپر بیان کیا گیا ہے، لیکن دیگر متغیرات کو خصوصی ایپلی کیشنز کے لیے تیار کیا گیا ہے، جیسے: فبونیکی حرکی ڈھیروں میں اضافہ حرکی ڈھیروں کی طرح دیگر حرکی ترجیحی قطاریں یہ ہیں: حرکی ہیٹر حرکی ہینگر حوالہ جات حرکی ڈیٹا ڈھانچے ڈھیروں (ڈیٹا ڈھانچے)