کوییپ کیست؟ توضیح بده.
در علوم کامپیوتر، کوییپ داده ساختاری به شکل صف اولویت می‌باشد. در این داده ساختار می‌توان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد. زمان تحلیل سرشکنی حذف هر عضو (مثلاً عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند. زمان سرشکن درج هر عضو عددی ثابت می‌باشد.کوییپ از یک لیست پیوندی دوطرفه و یک درخت ۲ -۴ تشکیل شده‌است که هرکدام از این داده ساختارها برای یافتن عضو با کمترین اولویت به کار گرفته می‌شود. تا زمانی که عمل حذفی انجام نشده باشد، هر عضو جدیدی که بخواهد وارد کوییپ شود، آن عضو مستقیماً وارد لیست پیوندی می‌شود. هنگامی که یکی از اعضای لیست حذف شود، تمامی اعضا بهدرخت ۲ - ۴ انتقال داده می‌شوند. برخلاف معمول که اعضا بر حسب اولویت ذخیره می‌شوند، درخت ۲ - ۴ اعضا را به ترتیب ورودی ذخیره می‌کند.داده ساختار و اسم آن توسط جان لاکنو و استفان لانگرمن طراحی شده‌است.توضیحات.کوییپ یک صف اولویت است که در زمان تحلیل سرشکن (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-4 انجام می‌شود.درخت ۲-۴ زمانی که یک عمل حذف اتفاق بیفتد استفاده می‌شود. اگر عنصر X در درخت T وجود داشته باشد، این عنصر با استفاده از عمل حذف درخت ۲-۴ حذف می‌شود. در غیر این صورت، اگر این عنصر در لیست l , بیت متغیرش ۱ بود (قبلاً اضافه شده بود به لیست) آنگاه تمام عناصر موجود در لیست، به درخت ۲-۴ انتقال داده می‌شوند و سپس بیت متغیر همهٔ آن‌ها به صفر تبدیل می‌شود. پس از این عملیات، عنصر مورد نظر با استفاده از عملیات حذف در درخت ۲-۴ , حذف می‌شود. یک کوییپ تنها از ویژگی‌های درخت ۲-۴ استفاده می‌کند نه از درخت جستجو. ساختار اصلاح شدهٔ یک درخت ۲-۴ به شرح زیر است: فرض کنید لیست l شامل زیرمجموعه‌ای از عناصر: formula_1 ,formula_2 , formula_3، … formula_4 می‌باشد. زمانی که عمل حذف فراخوانی می‌شود، مجموعه‌ای از عناصری که در l ذخیره شده‌اند، به برگ‌های درخت ۲-۴ اضافه می‌شوند، به این ترتیب، عملیات توسط یک برگ ساختگی که حاوی یک کلید نامحدود است، انجام می‌شود. هر گرهٔ داخلی از درخت T, یک اشاره گرformula_5 دارد، که به کمترین عنصر در زیر درخت v اشاره می‌کند. هر گره داخلی روی مسیر P از ریشه تا formula_6 , یک اشاره گر formula_7 دارد، که به کمترین کلید درformula_8 اشاره می‌کند. اشاره گرهای formula_5 هر گرهٔ داخلی روی مسیر P, در نظر گرفته نمی‌شوند. کوییپ یک اشاره گر به formula_10 دارد که به کوچکترین عنصر در T اشاره می‌کند.کاربرد کوییپ شامل مجموعهٔ منحصر به فردی از رویدادهای با اولویت بالا و پیدا کردن رویداد با بالاترین اولویت برای پردازش است.عملیات.در این مرحله L نماد لینک لیست دوطرفه، minL اشاره گر به کوچکترین عضو موجود در لیست T، L نماد درخت ۲ - ۴، formula_11 کوچکترین عضو ذخیره شده در k، T تعداد اعضای ذخیرهشده در q، T نماد کوییپ و n تعداد تمامی اعضای ذخیره شده در کوییپ می‌باشد.در زیر عملیاتی را که با کوییپ می‌توان انجام داد را توضیح می‌دهیم:-(New(Q: یک کوییپ جدید و خالی ایجاد می‌کند.با این کار لیست خالی L و درخت خالی T ایجاد می‌شود. مقدار k و n هم برابر ۰ گذاشته می‌شود.-(Insert(Q,x: عنصر x را به کوییپ Q اضافه می‌کند.عنصر x در لیست L وارد می‌شود. بیت متغیر عنصر x را برابر ۱ قرار می‌دهد تا نشان دهد این عنصر در لیست موجود می‌باشد. اگر x کوچکترین عنصر لیست باشد، مقدار minL به روزرسانی می‌شود. مقدار n هم به علاوهٔ ۱ خواهد شد.- (Minimum(Q: کوچکترین عنصر موجود در Q را دریافت می‌کند.اگر مقدار formula_12 کمتر از formula_13 باشد، minL برگردانده می‌شود در غیراین صورت خود formula_11 بازگردانده می‌شود.-(Delete(Q,x: عنصر x را از کوییپ Q حذف می‌کند.اگر بیت متغیر عنصر x برابر ۱ باشد، آن عنصر در لیست L ذخیره شده‌است. تمام عناصر لیست L را به درخت T منتقل می‌کنیم و بیت متغیرشان را برابر ۰ قرار می‌دهیم. به کمک عملگر درج درخت ۲ - ۴، هر عنصر به پدر راست‌ترین فرزند درخت T اضافه می‌شود. بدین ترتیب لیست L خالی می‌شود. مقدار formula_5 برای تمام گره‌های زیر درخت v که دارای فرزند جدیدی شده‌اند یا فرزند قبلیشان تغییر یافته‌است، به روز رسانی می‌شود. این کار را برای پدر گره هم انجام می‌دهیم و تا جایی که به ریشهٔ درخت برسیم این عمل را تکرار می‌کنیم.مقدار formula_7 تمام گره‌های موجود در مسیر ریشه تا formula_6 بایستی به روزرسانی شود. مقدار k نیز بایستی برابر n قرار بگیرد.اما اگر بیت متغیر عنصر x صفر باشد، گره x در درخت T برگ می‌باشد. به کمک عملگر حذف درخت ۲ - ۴، عنصر x را حذف می‌کنیم. با حرکت از گره x به سمت formula_6، متغیرهای formula_5 و formula_20 هر گره را به روزرسانی می‌کنیم. n و k را نیز به مقدار ۱ واحد کم می‌کنیم.-(DeleteMin(Q: کمترین عنصر موجود در کوییپ را برمی گرداند و سپس حذفش می‌کند.در واقع این تابع ابتدا، (Minimum(Q را صدا می‌زند و سپس تابع (Delete(Q,min را فراخوانی می‌کند و در آخر نیز مقدار min را برمی گرداند.-(CleanUp(Q: تمام عناصر موجود در لیست L و درخت T را حذف می‌کند. از اولین عنصر L شروع می‌کند و با پیمودن لیست، هر گره را حذف می‌کند. از ریشهٔ درخت T شروع می‌کند و با پیمایش پس ترتیب آن، اقدام به حذف همهٔ گره‌ها می‌کند.تجزیه و تحلیل.زمان اجرا با استفاده از زمان تحلیل سرشکن تحلیل می‌شود. تابع پتانسیل برای کوییپ Q, برابر با formula_21 خواهد بود که formula_22 است.-(Insert(Q, x: که هزینهٔ این عمل (O(1 است. اندازه لیست L یک عدد افزایش می‌یابد، پتانسیل با ثابت Cافزایش می‌یابد.-(Minimum(Q :این عمل موجب تغییر در ساختمان داده ی ما نمی‌شود بنابراین هزینه سرشکن آن برابر با (O(1 خواهد بود.-(Delete(Q, x: برای حذف دو حالت وجود دارد:حالت اول.اگر x در درخت T باشد، هزینهٔ سرشکن آن تغییر نمی‌کند. در درخت ۲-۴ هزینهٔ سرشکن عمل حذف برابر با (O(1 خواهد بود. زمانی که عنصر x از درخت حذف شود، اشاره گرهای formula_5 و formula_7 ممکن است لازم شود که به روز رسانی شوند. معمولاً عملیات به روز رسانی درformula_25 اتفاق میفتد.حالت دوم.اگر x در لیست L باشد، تمام عناصر L در T درج می‌شوند. هزینهٔ سرشکن روی درخت ۲-۴ برابر با formula_26 است، که a ضریب ثابتی است که در طول L ضرب می‌شود. پس از درج و به روز رسانی اشاره گرهای formula_5 و formula_7 , مجموع زمان صرف شده، به formula_29 محدود می‌شود. سپس عنصر x از درخت T حذف می‌شود، روی مسیری که از x تا formula_6 حرکت می‌شود و مقدارهای formula_5 و formula_7 تصحیح می‌شوند. معمولاً زمان صرف شده برابر با formula_33 است. اگر formula_34 باشد، سپس هزینهٔ سرشکن آن برابر با formula_25 خواهد بود.کد نمونه.یک پیاده‌سازی ساده از کوییپ را با جاوا نشان داده‌ایم: