کوییپ

کوییپ یک صف اولویت است که در زمان تحلیل سرشکن (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 شامل زیرمجموعه‌ای از عناصر: ${\displaystyle x_1}$

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

در این مرحله L نماد لینک لیست دوطرفه، minL اشاره گر به کوچکترین عضو موجود در لیست T، L نماد درخت ۲ - ۴، ${\displaystyle C_{x_0}}$

در زیر عملیاتی را که با کوییپ می‌توان انجام داد را توضیح می‌دهیم:

-(New(Q: یک کوییپ جدید و خالی ایجاد می‌کند.

با این کار لیست خالی L و درخت خالی T ایجاد می‌شود. مقدار k و n هم برابر ۰ گذاشته می‌شود.

-(Insert(Q,x: عنصر x را به کوییپ Q اضافه می‌کند. عنصر x در لیست L وارد می‌شود. بیت متغیر عنصر x را برابر ۱ قرار می‌دهد تا نشان دهد این عنصر در لیست موجود می‌باشد. اگر x کوچکترین عنصر لیست باشد، مقدار minL به روزرسانی می‌شود. مقدار n هم به علاوهٔ ۱ خواهد شد.

- (Minimum(Q: کوچکترین عنصر موجود در Q را دریافت می‌کند. اگر مقدار ${\displaystyle key(minL)}$

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

اگر بیت متغیر عنصر x برابر ۱ باشد، آن عنصر در لیست L ذخیره شده‌است. تمام عناصر لیست L را به درخت T منتقل می‌کنیم و بیت متغیرشان را برابر ۰ قرار می‌دهیم. به کمک عملگر درج درخت ۲ - ۴، هر عنصر به پدر راست‌ترین فرزند درخت T اضافه می‌شود. بدین ترتیب لیست L خالی می‌شود. مقدار ${\displaystyle h_v}$

مقدار ${\displaystyle C_v}$

اما اگر بیت متغیر عنصر x صفر باشد، گره x در درخت T برگ می‌باشد. به کمک عملگر حذف درخت ۲ - ۴، عنصر x را حذف می‌کنیم. با حرکت از گره x به سمت ${\displaystyle x_0}$

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

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

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

زمان اجرا با استفاده از زمان تحلیل سرشکن تحلیل می‌شود. تابع پتانسیل برای کوییپ Q, برابر با ${\displaystyle Q=c|L|}$

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

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

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

اگر x در درخت T باشد، هزینهٔ سرشکن آن تغییر نمی‌کند. در درخت ۲-۴ هزینهٔ سرشکن عمل حذف برابر با (O(1 خواهد بود. زمانی که عنصر x از درخت حذف شود، اشاره گرهای ${\displaystyle h_v}$

اگر x در لیست L باشد، تمام عناصر L در T درج می‌شوند. هزینهٔ سرشکن روی درخت ۲-۴ برابر با ${\displaystyle a|L|}$

یک پیاده‌سازی ساده از کوییپ را با جاوا نشان داده‌ایم:

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;
        }
}