کوییپ
From Wikipedia, the free encyclopedia
در علوم کامپیوتر، کوییپ داده ساختاری به شکل صف اولویت میباشد. در این داده ساختار میتوان عملیات درج و حذف هر عنصر دلخواه و همچنین یافتن عضو با بالاترین اولویت را انجام داد. زمان تحلیل سرشکنی حذف هر عضو (مثلاً عضو آ) برابر است با لگاریتم تعداد اعضایی که قبل از درج عضو آ داخل ساختار قرار داشتند. زمان سرشکن درج هر عضو عددی ثابت میباشد.
کوییپ از یک لیست پیوندی دوطرفه و یک درخت ۲ -۴ تشکیل شدهاست که هرکدام از این داده ساختارها برای یافتن عضو با کمترین اولویت به کار گرفته میشود. تا زمانی که عمل حذفی انجام نشده باشد، هر عضو جدیدی که بخواهد وارد کوییپ شود، آن عضو مستقیماً وارد لیست پیوندی میشود. هنگامی که یکی از اعضای لیست حذف شود، تمامی اعضا به درخت ۲ - ۴ انتقال داده میشوند. برخلاف معمول که اعضا بر حسب اولویت ذخیره میشوند، درخت ۲ - ۴ اعضا را به ترتیب ورودی ذخیره میکند.
داده ساختار و اسم آن توسط جان لاکنو و استفان لانگرمن طراحی شدهاست.