نمایش مبدأ برای کوییپ

[[پرونده:Queap.svg|بندانگشتی|چپ| 350x260px |کوییپی با k=۶ و n=۹]]
در [[علوم کامپیوتر]]، '''کوییپ''' [[داده ساختار]]ی به شکل [[صف اولویت]] می‌باشد. در این داده ساختار می‌توان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد. زمان [[تحلیل سرشکنی]] حذف هر عضو (مثلاً عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند. زمان سرشکن درج هر عضو عددی ثابت می‌باشد.

کوییپ از یک [[لیست پیوندی دوطرفه]] و یک [[درخت ۲-۳-۴|درخت ۲ -۴]] تشکیل شده‌است که هرکدام از این [[داده ساختارها]] برای یافتن عضو با کمترین اولویت به کار گرفته می‌شود. تا زمانی که عمل حذفی انجام نشده باشد، هر عضو جدیدی که بخواهد وارد کوییپ شود، آن عضو مستقیماً وارد [[لیست پیوندی]] می‌شود. هنگامی که یکی از اعضای لیست حذف شود، تمامی اعضا به
درخت ۲ - ۴ انتقال داده می‌شوند. برخلاف معمول که اعضا بر حسب اولویت ذخیره می‌شوند، درخت ۲ - ۴ اعضا را به ترتیب ورودی ذخیره می‌کند.

[[داده ساختار]] و اسم آن توسط جان لاکنو و استفان لانگرمن طراحی شده‌است.

== توضیحات ==

کوییپ یک صف اولویت است که در زمان تحلیل سرشکن (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 شامل زیرمجموعه‌ای از عناصر: <math>x_{1}</math> ,<math>x_{2}</math> , <math>x_{3}</math>، … <math>x_{k}</math> می‌باشد. زمانی که عمل حذف فراخوانی می‌شود، مجموعه‌ای از عناصری که در l ذخیره شده‌اند، به برگ‌های درخت ۲-۴ اضافه می‌شوند، به این ترتیب، عملیات توسط یک برگ ساختگی که حاوی یک کلید نامحدود است، انجام می‌شود. هر گرهٔ داخلی از درخت T, یک اشاره گر<math>h_{v}</math> دارد، که به کمترین عنصر در زیر درخت v اشاره می‌کند. هر گره داخلی روی مسیر P از ریشه تا <math>x_{0}</math> , یک [[اشاره گر]] <math>C_{v}</math> دارد، که به کمترین کلید در<math> T-T_{v}-{r} </math> اشاره می‌کند. اشاره گرهای <math>h_{v}</math> هر گرهٔ داخلی روی مسیر P, در نظر گرفته نمی‌شوند. کوییپ یک اشاره گر به <math>C_{x0}</math> دارد که به کوچکترین عنصر در T اشاره می‌کند.

کاربرد کوییپ شامل مجموعهٔ منحصر به فردی از رویدادهای با اولویت بالا و پیدا کردن رویداد با بالاترین اولویت برای پردازش است.

== عملیات ==

در این مرحله L نماد لینک لیست دوطرفه، minL اشاره گر به کوچکترین عضو موجود در لیست T، L نماد درخت ۲ - ۴، <math>C_{x_0}</math> کوچکترین عضو ذخیره شده در 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 را دریافت می‌کند.
اگر مقدار <math>key(minL)</math> کمتر از <math>key(c_{x_0})</math> باشد، minL برگردانده می‌شود در غیراین صورت خود <math>C_{x_0}</math> بازگردانده می‌شود.

'''-(Delete(Q,x:''' عنصر x را از کوییپ Q حذف می‌کند.

اگر بیت متغیر عنصر x برابر ۱ باشد، آن عنصر در لیست L ذخیره شده‌است. تمام عناصر لیست L را به درخت T منتقل می‌کنیم و بیت متغیرشان را برابر ۰ قرار می‌دهیم. به کمک عملگر درج درخت ۲ - ۴، هر عنصر به پدر راست‌ترین فرزند درخت T اضافه می‌شود. بدین ترتیب لیست L خالی می‌شود. مقدار <math>h_{v}</math> برای تمام گره‌های زیر درخت v که دارای فرزند جدیدی شده‌اند یا فرزند قبلیشان تغییر یافته‌است، به روز رسانی می‌شود. این کار را برای پدر گره هم انجام می‌دهیم و تا جایی که به ریشهٔ درخت برسیم این عمل را تکرار می‌کنیم.

مقدار <math>C_{v}</math> تمام گره‌های موجود در مسیر ریشه تا <math>x_{0}</math> بایستی به روزرسانی شود. مقدار k نیز بایستی برابر n قرار بگیرد.

اما اگر بیت متغیر عنصر x صفر باشد، گره x در درخت T برگ می‌باشد. به کمک عملگر حذف درخت ۲ - ۴، عنصر x را حذف می‌کنیم. با حرکت از گره x به سمت <math>x_{0}</math>، متغیرهای <math>h_{v}</math> و <math>c_{v}</math> هر گره را به روزرسانی می‌کنیم. n و k را نیز به مقدار ۱ واحد کم می‌کنیم.

'''-(DeleteMin(Q:''' کمترین عنصر موجود در کوییپ را برمی گرداند و سپس حذفش می‌کند.

در واقع این تابع ابتدا، (Minimum(Q را صدا می‌زند و سپس تابع (Delete(Q,min را فراخوانی می‌کند و در آخر نیز مقدار min را برمی گرداند.

'''-(CleanUp(Q:''' تمام عناصر موجود در لیست L و درخت T را حذف می‌کند. از اولین عنصر L شروع می‌کند و با پیمودن لیست، هر گره را حذف می‌کند. از ریشهٔ درخت T شروع می‌کند و با [[پیمایش گراف|پیمایش پس ترتیب]] آن، اقدام به حذف همهٔ گره‌ها می‌کند.

== تجزیه و تحلیل ==
زمان اجرا با استفاده از زمان تحلیل سرشکن تحلیل می‌شود. تابع پتانسیل برای کوییپ Q, برابر با <math> Q= c|L| </math> خواهد بود که <math> Q=(T,L) </math> است.

'''-(Insert(Q, x:''' که هزینهٔ این عمل (O(1 است. اندازه لیست L یک عدد افزایش می‌یابد، پتانسیل با ثابت Cافزایش می‌یابد.

'''-(Minimum(Q :'''این عمل موجب تغییر در [[ساختمان داده]] ی ما نمی‌شود بنابراین هزینه سرشکن آن برابر با (O(1 خواهد بود.

'''-(Delete(Q, x:''' برای حذف دو حالت وجود دارد:

== حالت اول ==

اگر x در درخت T باشد، هزینهٔ سرشکن آن تغییر نمی‌کند. در درخت ۲-۴ هزینهٔ سرشکن عمل حذف برابر با (O(1 خواهد بود. زمانی که عنصر x از درخت حذف شود، اشاره گرهای <math>h_{v}</math> و <math>C_{v}</math> ممکن است لازم شود که به روز رسانی شوند. معمولاً عملیات به روز رسانی در<math> O(lgq(x)) </math> اتفاق میفتد.

== حالت دوم ==

اگر x در لیست L باشد، تمام عناصر L در T درج می‌شوند. هزینهٔ سرشکن روی درخت ۲-۴ برابر با <math> a|L| </math> است، که a ضریب ثابتی است که در طول L ضرب می‌شود. پس از درج و به روز رسانی اشاره گرهای <math>h_{v}</math> و <math>C_{v}</math> , مجموع زمان صرف شده، به <math> 2a|L| </math> محدود می‌شود. سپس عنصر x از درخت T حذف می‌شود، روی مسیری که از x تا <math>x_{0}</math> حرکت می‌شود و مقدارهای <math>h_{v}</math> و <math>C_{v}</math> تصحیح می‌شوند. معمولاً زمان صرف شده برابر با <math> 2a|L| + O(lgq(x)) </math> است. اگر <math> c>2a </math> باشد، سپس هزینهٔ سرشکن آن برابر با <math> O(lgq(x)) </math> خواهد بود.

== کد نمونه ==

یک پیاده‌سازی ساده از کوییپ را با [[جاوا (زبان برنامه‌نویسی)|جاوا]] نشان داده‌ایم:
{{چپ‌چین}}
<pre>
public class Queap
{
        public int n, k;
        public List<Element> l;//Element is a generic data type
        public QueapTree t;//a 2-4 tree, modified for Queap purpose
        public Element minL;

        private Queap() {
                n = ۰;
                k = ۰;
                l = new LinkedList<Element>();
                t = new QueapTree();
        }

        public static Queap New() {
                return new Queap();
        }

        public static void Insert(Queap Q, Element x) {
                if (Q.n == ۰)
                        Q.minL = x;
                Q.l.add(x);
                x.inList = true;
                if (x.compareTo(Q.minL) <0)
                        Q.minL = x;
        }

        public static Element Minimum(Queap Q) {
//t is a 2-4 tree and x0, cv are tree nodes.
                if (Q.minL.compareTo(Q.t.x0.cv.key) <0)
                        return Q.minL;

                return Q.t.x0.cv.key;
        }

        public static void Delete(Queap Q, QueapNode x) {
                Q.t.deleteLeaf(x);
                --Q.n;
                --Q.k;
        }

        public static void Delete(Queap Q, Element x) {
                QueapNode n;
                if (x.inList) {
//set inList of all the elements in the list to false
                        n = Q.t.insertList(Q.l, x);
                        Q.k = Q.n;
                        Delete(Q, n);
                }
                else if ((n = Q.t.x0.cv).key == x)
                        Delete(Q, n);
        }

        public static Element DeleteMin(Queap Q) {
                Element min = Minimum(Q);
                Delete(Q, min);
                return min;
        }
}
</pre>
{{پایان چپ‌چین}}

== منابع ==
* {{یادکرد-ویکی
|پیوند=http://en.wikipedia.org/wiki/Queap
|عنوان=Queap |زبان=انگلیسی
|بازیابی=۹ مه ۲۰۱۴
}}
{{پانویس}}

[[رده:نظریه الگوریتمی اطلاعات]]
[[رده:هرم‌ها (علوم رایانه)]]
[[رده:داده ساختارهای استهلاکی]]