. متن داده‌شده را خلاصه کن

متن: کوییپ یک صف اولویت است که در زمان تحلیل سرشکن (۱) o می‌توان عناصر را در آن درج کرد، و حذف کمترین عنصر در زمان ((o (log (k+ ۲ انجام می‌شود، که k تعداد عناصری است که بسیار قبل‌تر از حذف عنصر مورد نظر، در هرم قرار داده شده‌اند. کوییپ یک ویژگی دارد که به آن خاصیت کیوییش queueish گفته می‌شود: پیدا کردن عنصر x در زمان ((o (lg q (x صورت می‌گیرد، که (q (x برابر با (n - ۱ - w (x است، و (w (x تعداد عناصر متمایزی است که توسط عملیاتی مثل جستجو، درج وحذف قابل‌دسترسی می‌باشند. (q (x تعداد عناصری است که پس از آخرین دسترسی به عنصر x , غیرقابل دسترسی هستند. در واقع خاصیت کیوییش، مکمل خاصیت درخت اسپلی عمل می‌کند: زمان جستجو عنصر x در ((o (lg w (x است. یک کوییپ می‌تواند با دو داده ساختار پیاده‌سازی شود: یک لیست پیوندی دو طرفه و یک نسخه اصلاح‌شده از درخت ۲ - ۴. لیست پیوندی دو سویه l , برای یک سری از عملیات درج و قرار دادن کمترین عنصر استفاده می‌شود. کوییپ یک اشاره‌گر به کمترین عنصر ذخیره‌شده در لیست، در خود نگه می‌دارد. برای اضافه کردن عنصر x به لیست l, عنصر x به انتهای لیست اضافه می‌شود و بیت متغیر این عنصر به ۱ تبدیل می‌شود. این عمل به منظور مشخص کردن این موضوع که عنصر مورد نظر در لیست وجود دارد یا درخت ۲ - ۴ انجام می‌شود. درخت ۲ - ۴ زمانی که یک عمل حذف اتفاق بیفتد استفاده می‌شود. اگر عنصر x در درخت t وجود داشته باشد، این عنصر با استفاده از عمل حذف درخت ۲ - ۴ حذف می‌شود. در غیر این صورت، اگر این عنصر در لیست l , بیت متغیرش ۱ بود (قبلا اضافه‌شده بود به لیست) آنگاه تمام عناصر موجود در لیست، به درخت ۲ - ۴ انتقال داده می‌شوند و سپس بیت متغیر همه آن‌ها به صفر تبدیل می‌شود. پس از این عملیات، عنصر مورد نظر با استفاده از عملیات حذف در درخت ۲ - ۴ , حذف می‌شود. یک کوییپ تنها از ویژگی‌های درخت ۲ - ۴ استفاده می‌کند نه از درخت جستجو. ساختار اصلاح شده یک درخت ۲ - ۴ به شرح زیر است: فرض کنید لیست l شامل زیرمجموعه‌ای از عناصر: , ,، … می‌باشد. زمانی که عمل حذف فراخوانی می‌شود، مجموعه‌ای از عناصری که در l ذخیره شده‌اند، به برگ‌های درخت ۲ - ۴ اضافه می‌شوند، به این ترتیب، عملیات توسط یک برگ ساختگی که حاوی یک کلید نامحدود است، انجام می‌شود. هر گره داخلی از درخت t, یک اشاره‌گر دارد، که به کمترین عنصر در زیر درخت v اشاره …
خلاصه:
در علوم کامپیوتر ، کوییپ داده ساختاری به شکل صف اولویت می‌باشد . در این داده ساختار می‌توان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد . زمان تحلیل سرشکنی حذف هر عضو (مثلا عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند . زمان سرشکن درج هر عضو عددی ثابت می‌باشد . کوییپ از یک لیست پیوندی دوطرفه و یک درخت ۲ -۴ تشکیل شده‌است که هرکدام از این داده ساختارها برای یافتن عضو با کمترین اولویت به کار گرفته می‌شود . تا زمانی که عمل حذفی انجام نشده باشد ، هر عضو جدیدی که بخواهد وارد کوییپ شود ، آن عضو مستقیما وارد لیست پیوندی می‌شود .