کوییپ

در علوم کامپیوتر، کوییپ داده ساختاری به شکل صف اولویت می‌باشد. در این داده ساختار می‌توان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد. زمان تحلیل سرشکنی حذف هر عضو (مثلاً عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند. زمان سرشکن درج هر عضو عددی ثابت می‌باشد.

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

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

عملیات

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

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

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

مقدار ${\displaystyle C_{v}}$ تمام گره‌های موجود در مسیر ریشه تا ${\displaystyle x_{0}}$ بایستی به روزرسانی شود. مقدار k نیز بایستی برابر n قرار بگیرد.

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

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

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

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

تجزیه و تحلیل

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

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

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

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

حالت اول

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

حالت دوم

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

کد نمونه

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

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

منابع

• مشارکت‌کنندگان ویکی‌پدیا. «Queap». در دانشنامهٔ ویکی‌پدیای انگلیسی، بازبینی‌شده در ۹ مه ۲۰۱۴.