موضوع مقاله: کوییپ | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # کوییپ | مقدمه: در این داده ساختار می‌توان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد. | ## بخش 1: کوییپ | زمان تحلیل سرشکنی حذف هر عضو (مثلاً عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند. کوییپ از یک لیست پیوندی دوطرفه و یک درخت ۲ -۴ تشکیل شده‌است که هرکدام از این داده ساختارها برای یافتن عضو با کمترین اولویت به کار گرفته می‌شود. تا زمانی که عمل حذفی انجام نشده باشد، هر عضو جدیدی که بخواهد وارد کوییپ شود، آن عضو مستقیماً وارد لیست پیوندی می‌شود. هنگامی که یکی از اعضای لیست حذف شود، تمامی اعضا به درخت ۲ - ۴ انتقال داده می‌شوند. برخلاف معمول که اعضا بر حسب اولویت ذخیره می‌شوند، درخت ۲ - ۴ اعضا را به ترتیب ورودی ذخیره می‌کند. توضیحات کوییپ یک صف اولویت است که در زمان تحلیل سرشکن (1)O می‌توان عناصر را در آن درج کرد، و حذف کمترین عنصر در زمان O(log(k+2 انجام می‌شود، که K تعداد عناصری است که بسیار قبل تر از حذف عنصر مورد نظر، در هرم قرار داده شده‌اند. کوییپ یک ویژگی دارد که به آن خاصیت کیوییش queueish گفته می‌شود: پیدا کردن عنصر 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 به لیست l, عنصر X به انتهای لیست اضافه می‌شود و بیت متغیر این عنصر به 1 تبدیل می‌شود. | ## بخش 2: کوییپ | این عمل به منظور مشخص کردن این موضوع که عنصر مورد نظر در لیست وجود دارد یا درخت 2-4 انجام می‌شود. اگر عنصر X در درخت T وجود داشته باشد، این عنصر با استفاده از عمل حذف درخت ۲-۴ حذف می‌شود. در غیر این صورت، اگر این عنصر در لیست l , بیت متغیرش ۱ بود (قبلاً اضافه شده بود به لیست) آنگاه تمام عناصر موجود در لیست، به درخت ۲-۴ انتقال داده می‌شوند و سپس بیت متغیر همهٔ آن‌ها به صفر تبدیل می‌شود. پس از این عملیات، عنصر مورد نظر با استفاده از عملیات حذف در درخت ۲-۴ , حذف می‌شود. ساختار اصلاح شدهٔ یک درخت ۲-۴ به شرح زیر است: فرض کنید لیست l شامل زیرمجموعه‌ای از عناصر: , , ، … می‌باشد. زمانی که عمل حذف فراخوانی می‌شود، مجموعه‌ای از عناصری که در l ذخیره شده‌اند، به برگ‌های درخت ۲-۴ اضافه می‌شوند، به این ترتیب، عملیات توسط یک برگ ساختگی که حاوی یک کلید نامحدود است، انجام می‌شود. هر گرهٔ داخلی از درخت T, یک اشاره گر دارد، که به کمترین عنصر در زیر درخت v اشاره می‌کند. هر گره داخلی روی مسیر P از ریشه تا , یک اشاره گر دارد، که به کمترین کلید در اشاره می‌کند. کاربرد کوییپ شامل مجموعهٔ منحصر به فردی از رویدادهای با اولویت بالا و پیدا کردن رویداد با بالاترین اولویت برای پردازش است. عملیات در این مرحله L نماد لینک لیست دوطرفه، minL اشاره گر به کوچکترین عضو موجود در لیست T، L نماد درخت ۲ - ۴، کوچکترین عضو ذخیره شده در k، T تعداد اعضای ذخیره شده در q، T نماد کوییپ و n تعداد تمامی اعضای ذخیره شده در کوییپ می‌باشد. در زیر عملیاتی را که با کوییپ می‌توان انجام داد را توضیح می‌دهیم: -(New(Q: یک کوییپ جدید و خالی ایجاد می‌کند. | ## بخش 3: کوییپ | بیت متغیر عنصر x را برابر ۱ قرار می‌دهد تا نشان دهد این عنصر در لیست موجود می‌باشد. اگر مقدار کمتر از باشد، minL برگردانده می‌شود در غیراین صورت خود بازگردانده می‌شود. تمام عناصر لیست L را به درخت T منتقل می‌کنیم و بیت متغیرشان را برابر ۰ قرار می‌دهیم. به کمک عملگر درج درخت ۲ - ۴، هر عنصر به پدر راست‌ترین فرزند درخت T اضافه می‌شود. مقدار برای تمام گره‌های زیر درخت v که دارای فرزند جدیدی شده‌اند یا فرزند قبلیشان تغییر یافته‌است، به روز رسانی می‌شود. این کار را برای پدر گره هم انجام می‌دهیم و تا جایی که به ریشهٔ درخت برسیم این عمل را تکرار می‌کنیم. از ریشهٔ درخت T شروع می‌کند و با پیمایش پس ترتیب آن، اقدام به حذف همهٔ گره‌ها می‌کند. زمانی که عنصر x از درخت حذف شود، اشاره گرهای و ممکن است لازم شود که به روز رسانی شوند. هزینهٔ سرشکن روی درخت ۲-۴ برابر با است، که a ضریب ثابتی است که در طول L ضرب می‌شود. | ## جمع‌بندی | سپس عنصر x از درخت T حذف می‌شود، روی مسیری که از x تا حرکت می‌شود و مقدارهای و تصحیح می‌شوند.