Queap
کمپیوٹر سائنس میں، کویپ ایک ترجیحی قطار ڈیٹا ڈھانچہ ہے۔ اعداد و شمار کا ڈھانچہ صوابدیدی عناصر کو داخل کرنے اور حذف کرنے کے ساتھ ساتھ اعلی ترین ترجیحی عنصر کی بازیافت کی اجازت دیتا ہے۔ ہر حذف کرنے میں ان آئٹمز کی تعداد میں تخفیف شدہ وقت لگتا ہے جو ہٹائی گئی آئٹم سے زیادہ عرصے سے ڈھانچے میں موجود ہیں۔ داخل کرنے میں مسلسل ادائیگی کا وقت لگتا ہے۔ اعداد و شمار کا ڈھانچہ دوگنا منسلک فہرست اور 2 سے 4 درخت کے اعداد و شمار کے ڈھانچے پر مشتمل ہوتا ہے، ہر ایک کو اس کے کم از کم ترجیحی عنصر پر نظر رکھنے کے لیے تبدیل کیا جاتا ہے۔ ڈھانچے کا بنیادی کام یہ ہے کہ نئے داخل کردہ عناصر کو دوگنا منسلک فہرست میں رکھا جائے، یہاں تک کہ حذف ہونے سے فہرست کی اشیاء میں سے ایک کو ہٹا دیا جائے، جس مقام پر وہ سب 2 سے 4 درخت میں منتقل ہو جاتے ہیں۔ 2-4 درخت اپنے عناصر کو زیادہ روایتی ترجیحی ترتیب کے بجائے اندراج کی ترتیب میں محفوظ کرتا ہے۔ ڈیٹا ڈھانچہ اور اس کا نام دونوں جان آئکونو اور اسٹیفن لینجرمین نے وضع کیے تھے۔ وضاحت ایک کویپ ایک ترجیحی قطار ہے جو O (1) کے تخفیف شدہ وقت میں عناصر کو داخل کرتی ہے، اور O (لاگ (k + 2)) میں کم از کم عنصر کو ہٹا دیتی ہے اگر وہاں k آئٹمز ہیں جو نکالے جانے والے عنصر سے زیادہ عرصے سے ڈھیر میں ہیں۔ قطار میں ایک خاصیت ہوتی ہے جسے قطار کی خاصیت کہا جاتا ہے: عنصر 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 ٹری کا استعمال کیا جاتا ہے۔ اگر آئٹم x پہلے سے ہی ٹری T میں ہے، تو آئٹم کو 2-4 ٹری ڈیلیٹ آپریشن کا استعمال کرتے ہوئے ہٹا دیا جاتا ہے۔ بصورت دیگر، آئٹم x فہرست L میں ہے (یہ چیک کرکے کیا جاتا ہے کہ آیا بٹ متغیر سیٹ ہے)۔ فہرست ایل میں محفوظ تمام عناصر کو پھر 2 سے 4 ٹری میں شامل کیا جاتا ہے، جس سے ہر عنصر کے بٹ متغیر کو صفر پر سیٹ کیا جاتا ہے۔ اس کے بعد ایکس کو ٹی سے ہٹا دیا جاتا ہے۔ ایک قطار صرف 2 سے 4 درخت کی ساخت کی خصوصیات کا استعمال کرتی ہے، نہ کہ سرچ ٹری کا۔ ترمیم شدہ 2-4 درخت کا ڈھانچہ مندرجہ ذیل ہے۔ فرض کریں کہ فہرست L میں عناصر کا درج ذیل مجموعہ ہے: جب حذف کرنے کا عمل شروع کیا جاتا ہے، تو ایل میں ذخیرہ شدہ عناصر کے سیٹ کو اس ترتیب میں 2 سے 4 درخت کے پتوں میں شامل کیا جاتا ہے، جس کے بعد ایک ڈمی پتی ہوتی ہے جس میں ایک لامحدود کلید ہوتی ہے۔ T کے ہر اندرونی نوڈ میں ایک پوائنٹر ہوتا ہے، جو سبٹری v میں سب سے چھوٹی آئٹم کی طرف اشارہ کرتا ہے۔ راستے P پر ہر اندرونی نوڈ میں جڑ سے ایک پوائنٹر ہوتا ہے، جو سب سے چھوٹی کلید کی طرف اشارہ کرتا ہے۔ پی کے راستے پر ہر اندرونی نوڈ کے اشارے کو نظر انداز کر دیا جاتا ہے۔ قطار میں ایک اشارہ ہوتا ہے، جو ٹی میں سب سے چھوٹے عنصر کی طرف اشارہ کرتا ہے۔ قطاروں کے استعمال میں اعلی ترجیحی واقعات کا ایک منفرد مجموعہ اور پروسیسنگ کے لیے اعلی ترجیحی واقعہ کا نکالنا شامل ہے۔ آپریشنز من ایل ایل کو ایک پوائنٹر ہونے دیں جو دوگنا منسلک فہرست ایل میں کم از کم عنصر کی طرف اشارہ کرتا ہے، 2 سے 4 ٹری میں ذخیرہ شدہ کم از کم عنصر ہو، ٹی، کے ٹی میں ذخیرہ شدہ عناصر کی تعداد ہو، اور این کیوپ کیو میں ذخیرہ شدہ عناصر کی کل تعداد ہو۔ آپریشنز مندرجہ ذیل ہیں: نیا (ق): ایک نئی خالی قطار کو شروع کرتا ہے۔ خالی ڈبل لنکڈ لسٹ L اور 2-4 ٹری T کو شروع کریں۔ k اور n کو صفر پر سیٹ کریں۔ داخل کریں (ق، x): عنصر x کو قطار میں شامل کریں ق۔ عنصر x کو فہرست L میں داخل کریں۔ عنصر x میں بٹ کو ایک پر سیٹ کریں تاکہ یہ ظاہر ہو کہ عنصر فہرست L میں ہے۔ اگر x فہرست کا سب سے چھوٹا عنصر ہے تو MinL پوائنٹر کو اپ ڈیٹ کریں۔ n میں 1 کا اضافہ۔ کم از کم (ق): کیوپ ق سے سب سے چھوٹے عنصر پر پوائنٹر حاصل کریں۔ اگر کلید (MinL) <کلید () ہے، تو MinL واپس کریں۔ ورنہ واپس آ جائیں۔ حذف کریں (ق، x): کویپ ق سے عنصر x کو ہٹا دیں۔ اگر عنصر x کا بٹ ایک پر سیٹ کیا گیا ہے، تو عنصر کو فہرست L میں محفوظ کیا جاتا ہے۔ L سے T تک کے تمام عناصر کو شامل کریں، ہر عنصر کا بٹ صفر پر سیٹ کریں۔ ہر عنصر کو 2-4 درخت کے داخل کرنے کے عمل کا استعمال کرتے ہوئے ٹی کے دائیں سب سے زیادہ بچے کے والدین میں شامل کیا جاتا ہے۔ ایل خالی ہو جاتا ہے۔ ان تمام نوڈس v کے لیے نوٹیفکیشن اپ ڈیٹ کریں جن کے بچے نئے/ترمیم شدہ ہیں، اور اگلے والدین کے ساتھ اس عمل کو دہرائیں جب تک کہ والدین جڑ کے برابر نہ ہوں۔ جڑ سے نوڈ تک چلیں، اور اقدار کو اپ ڈیٹ کریں۔ k کو n کے برابر سیٹ کریں۔ اگر عنصر x کا بٹ صفر پر سیٹ کیا گیا ہے، تو x T کا پتی ہے۔ 2-4 ٹری ڈیلیٹ آپریشن کا استعمال کرتے ہوئے x کو حذف کریں۔ نوڈ ایکس سے شروع کرتے ہوئے، ٹی سے نوڈ تک چلیں، اپ ڈیٹ کریں اور پوائنٹ کریں۔ n اور k کو 1 سے کم کریں۔ ڈیلیٹ من (ق): کیوپ ق سے سب سے چھوٹے عنصر کو حذف کریں اور واپس کریں۔ کم از کم (ق) آپریشن کو مدعو کریں۔ آپریشن منٹ واپس کرتا ہے۔ ڈیلیٹ (ق، منٹ) آپریشن شروع کریں۔ منٹ واپس کریں۔ کلین اپ (ق): فہرست ایل اور ٹری ٹی کے تمام عناصر کو حذف کریں۔ فہرست ایل کے پہلے عنصر سے شروع کرتے ہوئے، ہر نوڈ کو حذف کرتے ہوئے فہرست کو عبور کریں۔ ٹری ٹی کی جڑ سے شروع کرتے ہوئے، ٹری میں موجود ہر نوڈ کو حذف کرتے ہوئے، پوسٹ آرڈر ٹریورسل الگورتھم کا استعمال کرتے ہوئے ٹری کو عبور کریں۔ تجزیہ چل رہے وقت کا تجزیہ امورٹائزڈ تجزیہ کا استعمال کرتے ہوئے کیا جاتا ہے۔ کویپ ق کے لیے پوٹینشل فنکشن کہاں ہوگا۔ داخل کریں (ق، x): آپریشن کی لاگت O (1) ہے۔ فہرست ایل کا سائز ایک سے بڑھتا ہے، صلاحیت میں کچھ مستقل اضافہ ہوتا ہے سی۔ کم از کم (ق): آپریشن ڈیٹا ڈھانچے کو تبدیل نہیں کرتا ہے لہذا ادائیگی کی لاگت اس کی اصل لاگت، او (1) کے برابر ہے۔ حذف کریں (ق، x): دو صورتیں ہیں۔ کیس 1 اگر x ٹری T میں ہے، تو ادائیگی شدہ لاگت میں ترمیم نہیں کی جاتی ہے۔ حذف کرنے کا عمل O (1) امورٹائزڈ 2-4 ٹری ہے۔ چونکہ x کو ٹری سے ہٹا دیا گیا تھا، اور پوائنٹرز کو اپ ڈیٹ کرنے کی ضرورت پڑ سکتی ہے۔ زیادہ سے زیادہ، اپ ڈیٹس ہوں گی۔ کیس 2 اگر x فہرست L میں ہے، تو L کے تمام عناصر T میں داخل کیے جاتے ہیں۔ اس کی قیمت کچھ مستقل a کی ہوتی ہے، جو 2 سے 4 درخت پر قابل ادائیگی ہوتی ہے۔ اور پوائنٹروں کو داخل کرنے اور اپ ڈیٹ کرنے کے بعد، خرچ کیا گیا کل وقت اس سے محدود ہوتا ہے۔ دوسرا عمل x کو T سے حذف کرنا، اور x سے x تک کے راستے پر چلنا، اور اقدار کو درست کرنا ہے۔ زیادہ سے زیادہ وقت گزارا جاتا ہے۔ اگر، تو ادائیگی کی لاگت ہوگی۔ حذف کریں (ق، x): کم از کم (ق) اور حذف کریں (ق، x) کی تخفیف شدہ لاگت کا اضافہ ہے، جو ہے۔ کوڈ کی مثال کویپ کا ایک چھوٹا جاوا نفاذ: پبلک کلاس کویپ {پبلک انٹ این، کے ؛ پبلک لسٹ <عنصر> ایل ؛// عنصر ایک عام ڈیٹا ٹائپ ہے۔ عوامی کویپ ٹری ٹی ؛// ایک 2-4 درخت، کویپ مقصد کے لیے ترمیم شدہ عوامی عنصر منی ایل ؛ نجی کویپ () {n = 0 ؛ k = 0 ؛ l = نئی لنکڈ لسٹ <عنصر> () ؛ t = نیا کویپ ٹری () ؛} عوامی جامد کویپ نیا () {نیا کویپ واپس کریں () ؛} عوامی جامد کویڈ داخل کریں (کویپ ق، عنصر x) {اگر (ق۔ ن = = = 0) Q.minL = x ؛ Q.l.add (x) ؛ x.inList = سچ ہے ؛ اگر (x.compareTo (Q.minL) <0) Q.minL = x ؛} عوامی جامد عنصر کم از کم (کویپ ق) { اگر (Q.minL.compareTo (Q.t.x0.cv. کلید) <0) واپسی Q.minL ؛ واپسی Q.t.x0.cv. کلید ؛} عوامی جامد کالعدم حذف کریں (کویپ ق، کویپ نوڈ x) {Q.t.deleteLeaf (x) ؛-- ق. ن ؛-- ق. ک ؛} عوامی جامد کالعدم حذف کریں (کویپ ق، عنصر x) {کویپ نوڈ ن ؛ اگر (x.inList) {// فہرست میں تمام عناصر کی فہرست کو غلط n = Q.t.insertList (Ql, x) پر سیٹ کریں ؛ ق. ک = ق. ن ؛ حذف کریں (ق، ن) ؛} بصورت دیگر اگر ((n = Q.t.x0.cv). کلید = = =