كويب

في علم الحاسوب ، تُعرف الطابور ذو الأولوية (queap) بأنه بنية بيانات قائمة انتظار ذات أولوية . تسمح هذه البنية بإضافة وحذف أي عناصر، بالإضافة إلى استرجاع العنصر ذي الأولوية الأعلى. يستغرق كل حذف وقتًا مُعدَّلًا يتناسب لوغاريتميًا مع عدد العناصر التي بقيت في البنية لفترة أطول من العنصر المحذوف. أما الإضافة فتستغرق وقتًا مُعدَّلًا ثابتًا.

تتكون بنية البيانات من قائمة مرتبطة ثنائياً وبنية بيانات شجرية من 2 إلى 4 ، تم تعديل كل منهما لتتبع العنصر ذي الأولوية الأدنى. وتتمثل الوظيفة الأساسية لهذه البنية في الاحتفاظ بالعناصر المُضافة حديثاً في القائمة المرتبطة ثنائياً، إلى أن يؤدي حذف أحد عناصر القائمة إلى إزالتها، وعندها تُنقل جميع العناصر إلى الشجرة من 2 إلى 4. وتخزن الشجرة من 2 إلى 4 عناصرها بترتيب الإضافة، بدلاً من الترتيب التقليدي المُرتب حسب الأولوية.

تم ابتكار كل من بنية البيانات واسمها بواسطة جون إياكونو وستيفان لانجرمان . ^{[ 1 ]}

الطابور ذو الأولوية (queap) هو طابور ذو أولوية يُدرج العناصر في زمن O (1) مُعدَّل، ويزيل أصغر عنصر في زمن O (log( k  +  2)) إذا كان هناك k عنصرًا موجودة في الكومة لفترة أطول من العنصر المراد استخراجه. يتميز الطابور ذو الأولوية بخاصية تُسمى خاصية الطابور التقريبية: زمن البحث عن العنصر x هو O(log q ( x ))، حيث q ( x ) يساوي n - 1 - w ( x )، و w ( x ) هو عدد العناصر المختلفة التي تم الوصول إليها من خلال عمليات مثل البحث أو الإدراج أو الحذف. يُعرَّف q ( x ) بأنه عدد العناصر التي لم يتم الوصول إليها منذ آخر وصول إلى x . في الواقع، تُعد خاصية الطابور التقريبية مكملة لخاصية مجموعة العمل في شجرة التوزيع: زمن البحث عن العنصر x هو O (log w ( x )).    

يمكن تمثيل قائمة الانتظار (queap) ببنيتين بيانات: قائمة مرتبطة ثنائياً ونسخة معدلة من شجرة 2-4. تُستخدم القائمة المرتبطة ثنائياً، L ، لسلسلة من عمليات الإضافة وتحديد أصغر عنصر. تحتفظ قائمة الانتظار بمؤشر إلى أصغر عنصر مُخزّن في القائمة. لإضافة العنصر x إلى القائمة l ، يُضاف العنصر x إلى نهاية القائمة ويُعيّن متغير بت في العنصر x إلى واحد. تُجرى هذه العملية لتحديد ما إذا كان العنصر موجوداً في القائمة أو في شجرة 2-4.

تُستخدم شجرة 2-4 عند إجراء عملية حذف. إذا كان العنصر x موجودًا بالفعل في الشجرة T ، يُحذف باستخدام عملية الحذف في شجرة 2-4. وإلا، يكون العنصر x موجودًا في القائمة L (يتم ذلك بالتحقق مما إذا كان متغير البت مُفعّلاً). تُضاف جميع العناصر المخزنة في القائمة L إلى شجرة 2-4، مع ضبط متغير البت لكل عنصر على الصفر. ثم يُحذف x من T.

تستخدم خوارزمية queap خصائص بنية الشجرة 2-4 فقط، وليس شجرة بحث. بنية الشجرة 2-4 المعدلة هي كما يلي. لنفترض أن القائمة L تحتوي على مجموعة العناصر التالية:${\displaystyle x_{1},x_{2},x_{3},\dots ,x_{k}}$عند استدعاء عملية الحذف، تُضاف مجموعة العناصر المخزنة في L إلى أوراق الشجرة 2-4 بهذا الترتيب، متبوعة بورقة وهمية تحتوي على مفتاح لانهائي. كل عقدة داخلية في T لها مؤشر${\displaystyle h_{v}}$، مما يشير إلى أصغر عنصر في الشجرة الفرعية v . كل عقدة داخلية على المسار P من الجذر إلى${\displaystyle x_{0}}$يحتوي على مؤشر${\displaystyle c_{v}}$، مما يشير إلى أصغر مفتاح في${\displaystyle T-T_{v}-\{r\}}$. ال${\displaystyle h_{v}}$يتم تجاهل مؤشرات كل عقدة داخلية على المسار P. يحتوي الطابور على مؤشر إلى${\displaystyle c_{x_{0}}}$، مما يشير إلى أصغر عنصر في T.

يتضمن تطبيق نظام الطوابير مجموعة فريدة من الأحداث ذات الأولوية العالية واستخراج الحدث ذي الأولوية الأعلى للمعالجة.

ليكن minL مؤشرًا يشير إلى أصغر عنصر في القائمة المرتبطة ثنائيًا L ،${\displaystyle c_{x_{0}}}$ليكن العنصر الأصغر المخزن في الشجرة T ( 2-4) ، وليكن k عدد العناصر المخزنة في T ، وليكن n العدد الإجمالي للعناصر المخزنة في الطابور Q. العمليات هي كما يلي:

New(Q): يقوم بتهيئة قائمة انتظار فارغة جديدة.

قم بتهيئة قائمة مرتبطة مزدوجة فارغة L وشجرة 2-4 T. اضبط k و n على الصفر.

Insert(Q, x): أضفالعنصر x إلى قائمة الانتظار Q.

أضف العنصر x إلى القائمة L. اضبط البت الموجود في العنصر x على واحد لإثبات وجوده في القائمة L. حدّث مؤشر minL إذا كان x هو أصغر عنصر في القائمة. زد قيمة n بمقدار 1.

Minimum(Q): استرجاع مؤشر إلى أصغر عنصر من قائمةالانتظار Q.

إذا كان مفتاح (minL) < مفتاح (${\displaystyle c_{x_{0}}}$)، أعد minL . وإلا، أعد${\displaystyle c_{x_{0}}}$.

حذف(Q، x): إزالةالعنصر x من قائمة الانتظار Q.

إذا كانت بتة العنصر x تساوي واحدًا، يُخزَّن العنصر في القائمة L. أضف جميع العناصر من L إلى T ، مع ضبط بتة كل عنصر على صفر. يُضاف كل عنصر إلى أصل الابن الأيمن لـ T باستخدام عملية الإدراج في شجرة 2-4. تصبح L فارغة. حدّث${\displaystyle h_{v}}$مؤشرات لجميع العقد v التي تكون أبنائها جديدة/معدلة، وكرر العملية مع الأب التالي حتى يصبح الأب مساويًا للجذر. انتقل من الجذر إلى العقدة ${\displaystyle x_{0}}$وتحديث${\displaystyle c_{v}}$القيم. اجعل قيمة k تساوي قيمة n .

إذا تم ضبط بت العنصر x على الصفر، فإن x ورقة من الشجرة T. احذف x باستخدام عملية حذف الشجرة 2-4. بدءًا من العقدة x ، انتقل في T إلى العقدة${\displaystyle x_{0}}$تحديث${\displaystyle h_{v}}$و${\displaystyle c_{v}}$المؤشرات. قلل قيمة n و k بمقدار 1.

DeleteMin(Q): حذفوإرجاع أصغر عنصر من مجموعة Q.

استدعِ عملية Minimum(Q) . تُعيد هذه العملية القيمة min . استدعِ عملية Delete(Q, min) . تُعيد هذه العملية القيمة min .

التنظيف (Q): حذف جميعالعناصر في القائمة L والشجرة T.

بدءاً من العنصر الأول في القائمة L ، قم باجتياز القائمة، وحذف كل عقدة.

بدءاً من جذر الشجرة T ، قم باجتياز الشجرة باستخدام خوارزمية اجتياز ما بعد الترتيب ، وحذف كل عقدة في الشجرة.

يتم تحليل وقت التشغيل باستخدام التحليل المُستهلك . ستكون دالة الجهد لـ queap Q هي${\displaystyle \phi (Q)=c|L|}$أين${\displaystyle Q=(T,L)}$.

إدراج(Q, x): تكلفة العملية هي O(1) . يزداد حجم القائمة L بمقدار واحد، ويزداد الاحتمال بمقدار ثابت c .

الحد الأدنى (Q): لا تغير العملية بنية البيانات، لذا فإن التكلفة المستهلكة تساوي تكلفتها الفعلية، O(1).

حذف(Q، x): هناك حالتان.

تطبيق جافا صغير لـ queap:

public class Queap { public int n , k ; public List <Element> l ; // Element هو نوع بيانات عام. public QueapTree t ; // شجرة 2-4، مُعدّلة لأغراض Queap public Element minL ;دالة خاصة Queap () { n = 0 ; k = 0 ; 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 == 0 ) 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 عبارة عن شجرة 2-4 و x0 و cv عبارة عن عقد شجرة. 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 ) { // تعيين inList لجميع العناصر في القائمة إلى 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 ; } }

• الطابور (بنية البيانات)
• شجرة متفرعة