كومة فيبوناتشي صارمة

📅 آخر تحديث: ٢٦ يوليو ٢٠٢٦
✍️ نُشر في: ٢٦ يوليو ٢٠٢٦
📷 يحتوي على 106 صور
الموسوعة الحرة

في علم الحاسوب ، تُعدّ كومة فيبوناتشي الصارمة بنية بيانات قائمة انتظار ذات أولوية ، تتميز بحدود زمنية منخفضة في أسوأ الحالات . وهي تُطابق الحدود الزمنية المُعدّلة لكومة فيبوناتشي في أسوأ الحالات. ولتحقيق هذه الحدود الزمنية، تحافظ أكوام فيبوناتشي الصارمة على عدة ثوابت من خلال إجراء تحويلات استعادة بعد كل عملية. ويمكن إجراء هذه التحويلات في وقت ثابت باستخدام هياكل بيانات مساعدة لتتبع انتهاكات الثوابت، ويضمن مبدأ التوزيع إمكانية إصلاح هذه الانتهاكات. وقد طُوّرت أكوام فيبوناتشي الصارمة في عام 2012 على يد جيرث إس. برودال ، وجورج لاغوجيانيس، وروبرت إي. تارجان ، مع تحديث لها في عام 2025. [ 1 ]

إلى جانب طوابير برودال ، تنتمي أكوام فيبوناتشي الصارمة إلى فئة من هياكل البيانات المثلى تقاربياً لطوابير الأولوية. [ 2 ] جميع العمليات على أكوام فيبوناتشي الصارمة تُنفذ في أسوأ الحالات بزمن ثابت باستثناء عملية حذف أصغر عنصر ، والتي تستغرق بالضرورة زمناً لوغاريتمياً. وهذا هو الأمثل، لأنه يمكن استخدام أي طابور أولوية لفرز قائمة منن{\displaystyle n}العناصر من خلال أداءن{\displaystyle n}عمليات الإدخال ون{\displaystyle n}عمليات حذف الحد الأدنى . [ 3 ] ومع ذلك، فإن أكوام فيبوناتشي الصارمة أبسط من طوابير برودال، التي تستخدم المصفوفات الديناميكية والعدادات الزائدة، [ 4 ] في حين أن كومة فيبوناتشي الصارمة تعتمد على المؤشرات فقط.

بناء

كومة فيبوناتشي صارمة
كومة فيبوناتشي صارمة بدون فقدان. العقدتان 5 و2 هما جذران نشطان. أشجارهما الفرعية النشطة هي أشجار ذات حدين.

كومة فيبوناتشي الصارمة هي شجرة واحدة تحقق خاصية الكومة الدنيا . أي أن مفتاح أي عقدة يكون دائمًا أصغر من أو يساوي مفتاح أبنائها. ونتيجةً لذلك، تقع العقدة ذات المفتاح الأدنى دائمًا في الجذر.

كما هو الحال في أكوام فيبوناتشي العادية، [ 5 ] تمتلك أكوام فيبوناتشي الصارمة بنى فرعية مشابهة لأكوام ذات الحدين . ولتحديد هذه البنى، نصنف كل عقدة إلى أحد نوعين. وعليه، نقدم التعريفات والقواعد التالية:

  • جميع العقد إما نشطة (ملونة باللون الأبيض ) أو سلبية (ملونة باللون الأحمر ) .
  • الجذر النشط هو عقدة نشطة ذات أصل سلبي.
  • العقدة السلبية القابلة للربط هي عقدة سلبية حيث تكون جميع فروعها سلبية (تعتبر العقدة السلبية التي ليس لها أبناء قابلة للربط).
  • رتبة العقدة النشطة هي عدد الأبناء النشطين الذين تمتلكهم .
  • إن فقدان عقدة نشطة هو عدد الأبناء النشطين الذين فقدتهم.
  • بالنسبة لأي عقدة، تقع العقد الفرعية النشطة على يسار العقد الفرعية السلبية.
  • الجذر النشط لا يفقد أي شيء.
  • الجذر مبني للمجهول.
  • تقع الأبناء السلبية القابلة للربط من الجذر على يمين الأبناء السلبية غير القابلة للربط.

الثوابت

الثابت 1: البنية
الأنا{\displaystyle i}الطفل الأكثر نشاطًا على اليمينجأنا{\displaystyle c_{i}}يفي شرط العقدة النشطة بما يلي:جأنا.رأنك+جأنا.لoss≥أنا-1{\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1}.

وبالتالي، يمكن اعتبار فقدان عقدة نشطة تعميمًا لـ "علامات" كومة فيبوناتشي . على سبيل المثال، الشجرة الفرعية التي تتكون فقط من عقد نشطة بفقدان صفري هي شجرة ذات حدين .

بالإضافة إلى ذلك، توجد عدة ثوابت تفرض حدودًا لوغاريتمية على ثلاث كميات رئيسية: عدد الجذور النشطة، والخسارة الكلية، ودرجات العقد. وهذا على عكس كومة فيبوناتشي العادية، التي تتميز بمرونة أكبر وتسمح بنمو الانتهاكات الهيكلية إلى رتبةيا(ن){\displaystyle O(n)}سيتم تنظيفها لاحقًا، لأنها بنية بيانات كسولة .

للمساعدة في الحفاظ على درجات العقد لوغاريتمية، تشارك كل عقدة غير جذرية أيضًا في قائمة انتظار.سؤال{\displaystyle Q}في القسم التالي، وفي بقية هذه المقالة، سنعرّف العدد الحقيقيR=2إل جي⁡ن+6{\displaystyle R=2\lg n+6}، أينن{\displaystyle n}يمثل عدد العقد في الكومة، وإل جي{\displaystyle \lg }يرمز إلى اللوغاريتم الثنائي .

الثابت الثاني: الجذور النشطة
يبلغ العدد الإجمالي للجذور النشطة على الأكثرR+1{\displaystyle R+1}.
الثابت 3: الخسارة الكاملة
إجمالي الخسارة في الكومة هو على الأكثرR+1{\displaystyle R+1}.
الثابت الرابع: درجة الجذر
درجة الجذر هي على الأكثرR+3{\displaystyle R+3}.
الثابت 5: الدرجات غير الجذرية
بالنسبة للعقدة النشطة ذات الخسارة الصفرية، تكون الدرجة على الأكثر2إل جي⁡(2ن-ص)+10{\displaystyle 2\lg(2n-p)+10}، أينص{\displaystyle p}موقعها فيسؤال{\displaystyle Q}(مع اعتبار 1 العنصر الأول). أما بالنسبة لجميع العقد الأخرى غير الجذرية، فإن الدرجة تكون على الأكثر2إل جي⁡(2ن-ص)+9{\displaystyle 2\lg(2n-p)+9}.
النتيجة 1: الدرجة القصوى
درجة أي عقدة غير جذرية هي على الأكثرR+6{\displaystyle R+6}.
دليل :
ويترتب على ذلك مباشرة من الثابت 5. بوضعص=0{\displaystyle p=0}لدينا
2إل جي⁡(2ن-0)+10=2إل جي⁡ن+12=R+6{\displaystyle 2\lg(2n-0)+10=2\lg n+12=R+6}
اللمة 1: أعلى رتبة
إذا تحققت الخاصية 1، فإن الرتبة القصوىر{\displaystyle r}أو أن أي عقدة نشطة تكون على الأكثرإل جي⁡ن+2ل+2{\displaystyle \lg n+{\sqrt {2L}}+2}، أينل{\displaystyle L}هي الخسارة الكاملة. [ 6 ]
دليل :
نعتمد على التناقض. ليكنx{\displaystyle x}كن عقدة نشطة ذات رتبة قصوىر{\displaystyle r}في كومة معن{\displaystyle n}العقد والخسارة الكليةل{\displaystyle L}وافترض أنر≥إل جي⁡ن+ك+1{\displaystyle r\geq \lg n+k+1}، أينك{\displaystyle k}هو أصغر عدد صحيح بحيثك(ك+1)/2≥ل{\displaystyle k(k+1)/2\geq L}هدفنا هو إثبات أن الشجرة الفرعيةتيx{\displaystyle T_{x}}متجذرة فيx{\displaystyle x}يتضمنن+1{\displaystyle n+1}العقد، وهذا تناقض لأنه لا يوجد سوىن{\displaystyle n}العقد في الكومة.
احذف جميع الأشجار الفرعية المتفرعة من العقد السلبية منتيx{\displaystyle T_{x}}وبذلك، تبقى العقد نشطة فقط. اقطع جميع أحفادx{\displaystyle x}التي تحتوي أشجارها الفرعية على أي عقدة ذات خسارة موجبة، وزيادة خسارة أبناءx{\displaystyle x}وبناءً على ذلك، مرة واحدة عن كل حفيد مفقود. الكميةرأنك+لoss{\displaystyle \mathrm {rank} +\mathrm {loss} }لم يطرأ أي تغيير على العقد المتبقية، مما يحافظ على الثابت 1. علاوة على ذلك، لا تزال الخسارة الإجمالية في حدود 1.ل{\displaystyle L}.
أطفالx{\displaystyle x}يتكون الآن من أشجار فرعية خالية من الخسائر وعقد طرفية ذات خسارة موجبة. حاليًا،تيx{\displaystyle T_{x}}يرضيجأنا.رأنك+جأنا.لoss≥أنا-1{\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} \geq i-1}لـأنا{\displaystyle i}الطفل الأيمنجأنا{\displaystyle c_{i}}لx{\displaystyle x}نجعل هذا مساواة تامة عن طريق تقليل خسارة كل منها أولاًجأنا{\displaystyle c_{i}}وتقليم أي أحفاد إذا لزم الأمر. بعد ذلك،جأنا.رأنك+جأنا.لoss=أنا-1{\displaystyle c_{i}.\mathrm {rank} +c_{i}.\mathrm {loss} =i-1}بالضبط. جميع أحفاد الآخرين منx{\displaystyle x}كما يتم تحويلها إلى أشجار فرعية ثنائية عن طريق تقليم الأبناء حسب الضرورة.
نحاول الآن إعادة بناء نسخة مصغرة منتيx{\displaystyle T_{x}}بالبدء بشجرة ذات حدين من الدرجةر{\displaystyle r}، يحتوي2ر{\displaystyle 2^{r}}العقد النشطة. نرغب في زيادة الخسارة إلىل{\displaystyle L}لكن احتفظ برتبةx{\displaystyle x}مثلر{\displaystyle r}وعدد العقد أقل ما يمكن. بالنسبة لشجرة ذات حدين من الدرجةر{\displaystyle r}يوجد طفل واحد من كل درجة من0{\displaystyle 0}لر-1{\displaystyle r-1}وبالتالي، هناكج{\displaystyle j}أحفاد النظامر-ج-1{\displaystyle r-j-1}إذا قمنا بإلغاء جميع الأحفاد الحاصلين على شهاداتهم≤ر-ك-1{\displaystyle \leq r-k-1}ثم قمنا بالقطع∑ج=1كج=ك(ك+1)/2{\textstyle \sum _{j=1}^{k}j=k(k+1)/2}الأحفاد، وهو ما يكفي لرفع الخسارة إلىل{\displaystyle L}جميع الأحفاد حاصلون على شهادات جامعية≤ر-ك-2{\displaystyle \leq r-k-2}ابقَ على قيد الحياة. دعها تنجو.w{\displaystyle w}أن يكون ابنx{\displaystyle x}مع درجة علميةر-ك-1{\displaystyle r-k-1}والخسارة صفر. بافتراض ذلك،ر-ك-1≥إل جي⁡ن{\displaystyle r-k-1\geq \lg n}، وw{\displaystyle w}هي شجرة ذات حدين كاملة، لذا فهي تحتوي على الأقل2إل جي⁡ن=ن{\displaystyle 2^{\lg n}=n}العقد. لأن هذا يعنيتيx{\displaystyle T_{x}}لديه على الأقلن+1{\displaystyle n+1}عند العقد، وصلنا إلى تناقض، وبالتالير<إل جي⁡ن+ك+1{\displaystyle r<\lg n+k+1}مع ملاحظة أنك<ك(ك+1)=2ل{\displaystyle k<{\sqrt {k(k+1)}}={\sqrt {2L}}}، نحصلر<إل جي⁡ن+2ل+2{\displaystyle r<\lg n+{\sqrt {2L}}+2}.
النتيجة الثانية: أعلى رتبة
إذا تحققت الثابتتان 1 و3 معًا، فإن أعلى رتبة هيR{\displaystyle R}.
دليل :
انطلاقاً من الثابت 3، لدينال≤R+1{\displaystyle L\leq R+1}وباستبدال هذا في اللمة 1، نحسب كما يلي:
ر≤إل جي⁡ن+2ل+2≤إل جي⁡ن+2(R+1)+2=إل جي⁡ن+4إل جي⁡ن+14+2≤إل جي⁡ن+(إل جي⁡ن)2+2⋅4إل جي⁡ن+42+2=إل جي⁡ن+(إل جي⁡ن+4)+2=R{\displaystyle {\begin{aligned}r&\leq \lg n+{\sqrt {2L}}+2\\&\leq \lg n+{\sqrt {2(R+1)}}+2\\&=\lg n+{\sqrt {4\lg n+14}}+2\\&\leq \lg n+{\sqrt {(\lg n)^{2}+2\cdot 4\lg n+4^{2}}}+2\\&=\lg n+(\lg n+4)+2\\&=R\end{aligned}}}

التحولات

تُعيد التحويلات التالية الثوابت المذكورة أعلاه بعد تنفيذ عملية قائمة الانتظار ذات الأولوية. هناك ثلاث كميات رئيسية نرغب في تقليلها: عدد الجذور النشطة، والخسارة الكلية في الكومة، ودرجة الجذر. يمكن تنفيذ جميع التحويلات فييا(1){\displaystyle O(1)}الوقت، وهو أمر ممكن من خلال الحفاظ على هياكل بيانات مساعدة لتتبع العقد المرشحة (الموصوفة في قسم التنفيذ). [ 6 ]

تقليل الجذور النشط

يتركx{\displaystyle x}وy{\displaystyle y}أن تكون جذورًا نشطة ذات رتبة متساويةر{\displaystyle r}وافترضx.كهـy≤y.كهـy{\displaystyle x.\mathrm {key} \leq y.\mathrm {key} }. وصلةy{\displaystyle y}باعتباره الطفل الأيسر منx{\displaystyle x}ورفع رتبةx{\displaystyle x}1. إذا كان الطفل الأيمنz{\displaystyle z}لx{\displaystyle x}سلبي، رابطz{\displaystyle z}إلى الجذر.

نتيجة ل،y{\displaystyle y}لم يعد الجذر نشطًا، لذا ينخفض ​​عدد الجذور النشطة بمقدار 1. ومع ذلك، قد تزداد درجة عقدة الجذر بمقدار 1.

منذy{\displaystyle y}يصبح(ر+1){\displaystyle (r+1)}الطفل الأيمن منx{\displaystyle x}، وy{\displaystyle y}لديه رتبةر{\displaystyle r}، يتم الحفاظ على الثابت 1.

الفرضية 2: توافر تقليل الجذر النشط
إذا تم انتهاك الثابت 2، ولكن الثابتين 1 و3 صحيحان، فإن اختزال الجذر النشط ممكن.
دليل :
بسبب كسر الثابت 2، يوجد أكثر منR+1{\displaystyle R+1}توجد جذور نشطة. من النتيجة 2، فإن أعلى رتبة للعقدة هيR{\displaystyle R}. وفقًا لمبدأ خانة الحمام ، يوجد زوج من الجذور النشطة من نفس الرتبة.

الحد من الخسائر

تقليل الخسائر في عقدة واحدة

يتركx{\displaystyle x}أن يكون مستخدمًا نشطًا غير مُجذّر مع فقدان لا يقل عن 2. رابطx{\displaystyle x}إلى الجذر، مما يحوله إلى جذر نشط، ويعيد ضبط خسارته إلى 0. دع الأصل الأصلي لـx{\displaystyle x}يكونy{\displaystyle y}.y{\displaystyle y}يجب أن يكون نشطًا، وإلاx{\displaystyle x}كانت ستكون في السابق جذرًا نشطًا، وبالتالي لا يمكن أن يكون لها خسارة إيجابية. رتبةy{\displaystyle y}يتم إنقاصها بمقدار 1. إذاy{\displaystyle y}إذا لم يكن جذرًا نشطًا، فقم بزيادة خسارته بمقدار 1.

بشكل عام، ينخفض ​​إجمالي الخسارة بمقدار 1 أو 2. وكأثر جانبي، تزداد درجة الجذر وعدد الجذور النشطة بمقدار 1، مما يجعلها أقل تفضيلاً من تقليل الخسارة بعقدتين، ولكنها لا تزال عملية ضرورية.

تقليل الخسارة بعقدتين

يترك x{\displaystyle x}و y{\displaystyle y} أن تكون عقدًا نشطة ذات رتبة متساوية ر{\displaystyle r}والخسارة تساوي 1، ولتكنz{\displaystyle z}كن والدًا لـy{\displaystyle y}دون الإخلال بعمومية المسألة ، افترض أنx.كهـy≤y.كهـy{\displaystyle x.\mathrm {key} \leq y.\mathrm {key} }افصلy{\displaystyle y}منz{\displaystyle z}، والرابطy{\displaystyle y}لx{\displaystyle x}زيادة رتبةx{\displaystyle x}بمقدار 1 وإعادة ضبط خسارةx{\displaystyle x}وy{\displaystyle y}من 1 إلى 0.

z{\displaystyle z}يجب أن يكون نشطًا، لأنy{\displaystyle y}كان لديه خسارة إيجابية، وبالتالي لم يكن من الممكن أن يكون جذرًا نشطًا. ومن ثم، فإن رتبةz{\displaystyle z}يتم إنقاصها بمقدار 1. إذاz{\displaystyle z}إذا لم يكن جذرًا نشطًا، فقم بزيادة خسارته بمقدار 1.

بشكل عام، ينخفض ​​إجمالي الخسارة بمقدار 1 أو 2، دون أي آثار جانبية.

اللمة 3: توافر تقليل الخسائر
إذا تم انتهاك الثابت 3 بواسطة 1، ولكن الثابت 2 صحيح، فإن تقليل الخسارة ممكن.
البرهان : نطبق مبدأ خانة الحمام مرة أخرى. إذا تم انتهاك الثابت 3 بواسطة 1، فإن الخسارة الكلية هيل=R+2{\displaystyle L=R+2}يمكن إعادة صياغة اللمة 1 لتعمل أيضًا معل=R+2{\displaystyle L=R+2}وبالتالي، فإن النتيجة الثانية صحيحة. بما أن الرتبة القصوى هيR{\displaystyle R}إما أن يكون هناك زوج من العقد النشطة ذات رتبة متساوية وخسارة 1، أو عقدة نشطة ذاتلoss≥2{\displaystyle \mathrm {loss} \geq 2}. كلا الحالتين توفران فرصة للحد من الخسائر.

اختزال درجة الجذر

اختزال درجة الجذر
اختزال درجة الجذر

يتركx{\displaystyle x}،y{\displaystyle y}، وz{\displaystyle z}لِتُكن العناصر الثلاثة الأخيرة من العنصر الجذر قابلة للربط السلبي. افصلها جميعًا عن العنصر الجذر ورتبها بحيث x.كهـy≤y.كهـy≤z.كهـy{\displaystyle x.\mathrm {key} \leq y.\mathrm {key} \leq z.\mathrm {key} }. يتغيرx{\displaystyle x}وy{\displaystyle y}أن تكون نشطًا. رابطz{\displaystyle z}لy{\displaystyle y}، وصلةy{\displaystyle y}لx{\displaystyle x}، والرابطx{\displaystyle x}باعتباره الابن الأيسر للجذر. ونتيجة لذلك،x{\displaystyle x}يصبح جذرًا نشطًا برتبة 1 وخسارة 0. رتبة وخسارةy{\displaystyle y}تم ضبطه على 0.

التغيير الصافي لهذا التحويل هو أن درجة العقدة الجذرية تنخفض بمقدار 2. وكأثر جانبي، يزداد عدد الجذور النشطة بمقدار 1.

اللمة 4: إمكانية اختزال درجة الجذر
إذا تم انتهاك الثابت 4، ولكن الثابت 2 صحيح، فإن تقليل درجة الجذر ممكن.
دليل :
إذا تم كسر الثابت 4، فإن درجة الجذر تكون على الأقلR+4{\displaystyle R+4}تنقسم فروع الجذر إلى ثلاث فئات: الجذور النشطة، والعقد غير القابلة للربط، والعقد غير القابلة للربط. كل عقدة غير قابلة للربط تحتوي على جذر نشط، لأن شجرتها الفرعية تضم عقدة نشطة واحدة على الأقل. ولأن عدد الجذور النشطة لا يتجاوزR+1{\displaystyle R+1}لذلك، يجب أن تكون العناصر الثلاثة الأخيرة من الجذر قابلة للربط السلبي.

ملخص

يلخص الجدول التالي تأثير كل تحويل على الكميات الثلاث المهمة. قد يُخلّ كل تحويل على حدة بالثوابت، لكننا مهتمون فقط ببعض تركيبات التحويلات التي لا تزيد أيًا من هذه الكميات.

تأثير التحولات
الجذور النشطةخسارة كاملةالدرجة الجذرية
تقليل الجذور النشط-1{\displaystyle -1}0{\displaystyle 0}0 أو +1{\displaystyle 0{\text{ or }}{+}1}
اختزال درجة الجذر+1{\displaystyle +1}0{\displaystyle 0}-2{\displaystyle -2}
تقليل الخسائر في عقدة واحدة+1{\displaystyle +1}على الأقل -1{\displaystyle {\text{at least }}{-}1}+1{\displaystyle +1}
تقليل الخسارة بعقدتين0{\displaystyle 0}-1 أو -2{\displaystyle -1{\text{ or }}{-}2}0{\displaystyle 0}

عند تحديد التحويلات التي يجب إجراؤها، نأخذ في الاعتبار أسوأ تأثير محتمل لهذه العمليات فقط، تبسيطًا للأمر. كما نعتبر نوعي تقليل الخسائر عملية واحدة. وبناءً على ذلك، نُعرّف "إجراء تقليل الخسائر" بأنه محاولة كل نوع من أنواع تقليل الخسائر على حدة.

أسوأ تأثير للتحولات
الجذور النشطةخسارة كاملةالدرجة الجذرية
تقليل الجذور النشط-1{\displaystyle -1}0{\displaystyle 0}+1{\displaystyle +1}
اختزال درجة الجذر+1{\displaystyle +1}0{\displaystyle 0}-2{\displaystyle -2}
الحد من الخسائر+1{\displaystyle +1}-1{\displaystyle -1}+1{\displaystyle +1}

تطبيق

عقد الربط

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

بالنسبة للعقدة الجذرية، نشترط أيضًا أن تقع العقد الفرعية القابلة للربط السلبي على يمين العقد الفرعية غير القابلة للربط السلبي. ولأننا نرغب في ربط العقد بالعقدة الجذرية في وقت ثابت، يجب الاحتفاظ بمؤشر إلى أول عقدة فرعية قابلة للربط السلبي للعقدة الجذرية.

إيجاد العقد المرشحة

تعتمد التحويلات الثابتة المُستعادة على القدرة على إيجاد العقد المرشحة فييا(1){\displaystyle O(1)}الوقت. هذا يعني أنه يجب علينا تتبع الجذور النشطة ذات الرتبة نفسها، والعقد ذات الخسارة 1 من الرتبة نفسها، والعقد ذات الخسارة 2 على الأقل.

وصفت الورقة الأصلية التي كتبها برودال وآخرون قائمة ثابتة وقائمة ترتيب كطريقة لتتبع العقد المرشحة. [ 6 ]

قائمة الإصلاحات

قائمة الترتيب وقائمة الإصلاح
قائمة الترتيب وقائمة الإصلاح

تنقسم قائمة الإصلاحات إلى أربعة أجزاء:

  1. الجذور النشطة جاهزة لتقليص الجذور النشطة - الجذور النشطة التي لها شريك من نفس الرتبة. يتم الاحتفاظ بالعقد ذات الرتبة نفسها متجاورة.
  2. الجذور النشطة غير جاهزة بعد للاختزال النشط - الجذور النشطة الوحيدة لتلك الرتبة.
  3. العقد النشطة ذات الخسارة 1 والتي لم تصبح جاهزة بعد لتقليل الخسارة - العقد النشطة الوحيدة ذات الخسارة 1 لهذا الترتيب.
  4. العقد النشطة الجاهزة لتقليل الخسائر – يشمل ذلك العقد النشطة ذات الخسارة 1 والتي لها شريك من نفس الرتبة، والعقد النشطة ذات الخسارة 2 على الأقل، والتي لا تحتاج إلى تقليل خسائر الشركاء. تُحفظ العقد ذات الرتبة نفسها متجاورة.

للتحقق من إمكانية تقليل الجذر النشط، نتحقق ببساطة مما إذا كان الجزء 1 غير فارغ. إذا كان غير فارغ، يمكن حذف أول عقدتين وتحويلهما. وبالمثل، للتحقق من إمكانية تقليل الخسارة، نتحقق من نهاية الجزء 4. إذا احتوى على عقدة بخسارة لا تقل عن 2، يتم تقليل خسارة عقدة واحدة. وإلا، إذا كانت آخر عقدتين لهما خسارة 1، ولهما نفس الرتبة، يتم تقليل خسارة عقدتين.

قائمة التصنيف

قائمة الرتب هي قائمة مرتبطة بشكل مزدوج تحتوي على معلومات حول كل رتبة، للسماح بربط العقد من نفس الرتبة معًا في قائمة الثبات.

لكل عقدة تمثل رتبةر{\displaystyle r}في قائمة الترتيب، نحافظ على ما يلي:

  • مؤشر إلى أول جذر نشط في قائمة الإصلاحات ذات الرتبةر{\displaystyle r}إذا لم تكن هذه العقدة موجودة، فإن هذا يكون فارغًا (NULL).
  • مؤشر إلى أول عقدة نشطة في قائمة الإصلاح ذات الرتبةر{\displaystyle r}والخسارة 1. إذا لم تكن هذه العقدة موجودة، فهذا يعني أنها فارغة (NULL).
  • مؤشر إلى العقدة التي تمثل الرتبةر+1{\displaystyle r+1}ور-1{\displaystyle r-1}، لتسهيل زيادة الرتب ونقصانها.

تتطلب قائمة الإصلاح وقائمة الترتيب عمليات حفظ سجلات مكثفة، والتي يجب القيام بها كلما ظهرت عقدة نشطة جديدة، أو عند تغيير رتبة العقدة أو فقدانها.

العلم المشترك

قائمة بالعُقد داخل الذاكرة الديناميكية. تشير كل عقدة إلى علامة تُحدد ما إذا كانت نشطة أم غير نشطة. جميع العُقد النشطة تشير إلى نفس العلامة.
استخدام علامة مشتركة لتغيير جميع العقد وجعلها سلبية فييا(1){\displaystyle O(1)}وقت

تُحوّل عملية الدمج جميع العُقد النشطة في الكومة الأصغر إلى عُقد غير نشطة. ويمكن القيام بذلك فييا(1){\displaystyle O(1)}يتم ذلك عن طريق إضافة مستوى من التوجيه غير المباشر. [ 6 ] فبدلاً من استخدام علامة منطقية، تحتوي كل عقدة نشطة على مؤشر يشير إلى كائن علامة نشطة يحتوي على قيمة منطقية. بالنسبة للعقد غير النشطة، لا يهم أي كائن علامة نشطة تشير إليه، طالما أن كائن العلامة مضبوط على حالة سلبية، لأنه ليس من الضروري تحويل العديد من العقد غير النشطة إلى عقد نشطة في وقت واحد.

إعادة ربط المؤشرات بين العقد والمفاتيح المعبأة
إعادة ربط المؤشرات بين العقد والمفاتيح المعبأة

تخزين المفاتيح

تتطلب عملية تقليل المفتاح مرجعًا إلى العقدة التي نرغب في تقليل مفتاحها. ومع ذلك، فإن عملية تقليل المفتاح نفسها قد تبدل أحيانًا مفتاح العقدة مع مفتاح الجذر.

لنفترض أن عملية الإدراج تُرجع مرجعًا مبهمًا يمكننا استدعاء دالة `reduce-key` عليه، كجزء من واجهة برمجة التطبيقات العامة. إذا كانت هذه المراجع عبارة عن عُقد كومة داخلية، فإن تبديل المفاتيح يُغير هذه المراجع، مما يؤدي إلى أن تصبح مراجع أخرى غير مُعرّفة. لضمان بقاء المفتاح دائمًا مع نفس المرجع، من الضروري "تغليف" المفتاح. تحتوي كل عقدة كومة الآن على مؤشر إلى صندوق يحتوي على المفتاح، ويحتوي الصندوق أيضًا على مؤشر إلى عقدة الكومة. عند إدراج عنصر، نقوم بإنشاء صندوق لتخزين المفتاح فيه، ونربط عقدة الكومة بالصندوق في كلا الاتجاهين، ونُعيد كائن الصندوق. [ 6 ] لتبديل المفاتيح بين عقدتين، نعيد ربط المؤشرات بين الصناديق والعقد.

العمليات

دمج

يتركح1{\displaystyle h_{1}}وح2{\displaystyle h_{2}}كوّن أكوام فيبوناتشي صارمة. إذا كان أي منهما فارغًا، فأرجع الآخر. وإلا، دعهن1{\displaystyle n_{1}}ون2{\displaystyle n_{2}}لنفترض أن أحجامها المقابلة. وبدون فقدان للعمومية، افترض أنن1≤ن2{\displaystyle n_{1}\leq n_{2}}بما أن أحجام قائمة التثبيت وقائمة الترتيب لكل كومة تتناسب لوغاريتميًا مع حجم الكومة، فإنه لا يمكن دمج هذه البنى المساعدة في وقت ثابت. بدلاً من ذلك، نتخلص من بنية الكومة الأصغر.ح1{\displaystyle h_{1}}عن طريق حذف قائمة الإصلاح وقائمة الترتيب، وتحويل جميع عُقدها إلى عُقد سلبية. [ 6 ] يمكن القيام بذلك في وقت ثابت، باستخدام علامة مشتركة، كما هو موضح أعلاه. رابطح1{\displaystyle h_{1}}وح2{\displaystyle h_{2}}، مما يجعل الجذر ذو المفتاح الأصغر هو الأصل للآخر.سؤال1{\displaystyle Q_{1}}وسؤال2{\displaystyle Q_{2}}كن طوابير منح1{\displaystyle h_{1}}وح2{\displaystyle h_{2}}على التوالي. يتم تعيين قائمة انتظار الكومة الناتجة إلىسؤالمهـرزهـد=سؤال1+{رلأرزهـر}+سؤال2{\displaystyle Q_{\mathrm {merged} }=Q_{1}+\{r_{\mathrm {larger} }\}+Q_{2}}، أينرلأرزهـر{\displaystyle r_{\mathrm {larger} }}هو الجذر ذو المفتاح الأكبر.

الانتهاك البنيوي الوحيد المحتمل هو درجة الجذر. ويتم حل هذه المشكلة بإجراء عملية اختزال جذر نشطة واحدة، وعملية اختزال درجة جذر واحدة، إذا كان كل تحويل ممكنًا.

الجذور النشطةخسارة كاملةالدرجة الجذرية
الولاية بعد الدمج0{\displaystyle 0}0{\displaystyle 0}+1{\displaystyle +1}
1×{\displaystyle 1\times }تقليل الجذور النشط-1{\displaystyle -1}0{\displaystyle 0}+1{\displaystyle +1}
1×{\displaystyle 1\times }اختزال درجة الجذر+1{\displaystyle +1}0{\displaystyle 0}-2{\displaystyle -2}
المجموع0{\displaystyle 0}0{\displaystyle 0}0{\displaystyle 0}

إثبات صحة النتائج

تتحقق الثوابت 1 و2 و3 تلقائيًا، نظرًا لتجاهل بنية الكومة. وكما حُسب أعلاه، تُحل أي انتهاكات للثابت 4 عن طريق تحويل اختزال درجة الجذر.

للتحقق من الثابت 5، نأخذ في الاعتبار المواضع النهائية للعقد فيسؤال{\displaystyle Q}لكل عقدة درجة محدودة بـ2إل جي⁡(2ن-ص)+10{\displaystyle 2\lg(2n-p)+10}أو2إل جي⁡(2ن-ص)+9{\displaystyle 2\lg(2n-p)+9}.

للكومة الأصغرح1{\displaystyle h_{1}}المناصب فيسؤال1{\displaystyle Q_{1}}لم تتغير. ومع ذلك، فإن جميع العقد فيح1{\displaystyle h_{1}}أصبحت الآن سلبية، مما يعني أن قيدها قد يتغير من+10{\displaystyle +10}القضية إلى+9{\displaystyle +9}في هذه الحالة. ولكن مع ملاحظة ذلكن1≤ن2{\displaystyle n_{1}\leq n_{2}}الحجم الناتجن=ن1+ن2{\displaystyle n=n_{1}+n_{2}}هو ضعف على الأقلن1{\displaystyle n_{1}}وهذا يؤدي إلى زيادة لا تقل عن 1 في كل قيد، مما يزيل القلق السابق.

الجذر ذو المفتاح الأكبر بينح1{\displaystyle h_{1}}وح2{\displaystyle h_{2}}يصبح غير جذري، ويتم وضعه بينسؤال1{\displaystyle Q_{1}}وسؤال2{\displaystyle Q_{2}}في هذا المنصبن1{\displaystyle n_{1}}وبحسب الثابت 4، فإن درجته كانت محدودة إماR1+3=2إل جي⁡ن1+9{\displaystyle R_{1}+3=2\lg n_{1}+9}أوR2+3=2إل جي⁡ن2+9{\displaystyle R_{2}+3=2\lg n_{2}+9}، وذلك بحسب الكومة التي أتت منها. من السهل ملاحظة أن هذا أقل من2إل جي⁡(2ن1+2ن2-ن1)+9{\displaystyle 2\lg {(2n_{1}+2n_{2}-n_{1})}+9}على أي حال.

بالنسبة للكومة الأكبر، تزداد المواضع بمقدارن1{\displaystyle n_{1}}لكن بما أن الحجم الناتج هون=ن1+ن2{\displaystyle n=n_{1}+n_{2}}، القيمة2ن-ص{\displaystyle 2n-p}بل إنها تزيد، مما يضعف القيد.

أدخل

يمكن اعتبار عملية الإضافة حالة خاصة من عملية الدمج. لإضافة مفتاح واحد، يتم إنشاء كومة جديدة تحتوي على عقدة سلبية واحدة وقائمة انتظار فارغة، ثم يتم دمجها مع الكومة الرئيسية.

البحث عن الحد الأدنى

بسبب خاصية الكومة الدنيا، فإن العقدة ذات المفتاح الأدنى تكون دائمًا في الجذر، إن وجدت.

حذف الحد الأدنى

عملية حذف الحد الأدنى من كومة فيبوناتشي الصارمة
عملية حذف الحد الأدنى

إذا كانت العقدة الجذرية هي العقدة الوحيدة في الكومة، فإننا ننتهي ببساطة عن طريق إزالتها. وإلا، نبحث في أبناء العقدة الجذرية للعثور على العقدة.x{\displaystyle x}باستخدام مفتاح أدنى، وتعيين الجذر الجديد إلىx{\displaystyle x}. لوx{\displaystyle x}إذا كان نشطًا، فاجعله سلبيًا، مما يؤدي إلى حدوث خطأ في جميع الأبناء النشطين لـx{\displaystyle x}لتصبح جذورًا نشطة ضمنيًا. اربط أبناء الجذر القديم بـx{\displaystyle x}. منذx{\displaystyle x}الآن هو الجذر، انقل جميع العناصر الفرعية المرتبطة به بشكل سلبي إلى اليمين، ثم قم بإزالتهx{\displaystyle x}منسؤال{\displaystyle Q}.

تتضاعف درجة الجذر تقريبًا، لأننا ربطنا جميع أبناء الجذر القديم بـx{\displaystyle x}نقوم بإجراء التحولات الترميمية التالية:

  1. كرر مرتين: قم بالتدويرسؤال{\displaystyle Q}عن طريق تحريك الرأسy{\displaystyle y}لسؤال{\displaystyle Q}إلى الخلف، وقم بربط الطفلين السلبيين الموجودين في أقصى اليمين منy{\displaystyle y}إلى الجذر.
  2. إذا كان من الممكن تقليل الخسائر، فقم بذلك.
  3. قم بإجراء عمليات تقليل الجذور النشطة وتقليل درجة الجذر حتى يصبح أي منهما غير ممكن.

لمعرفة كيف أن الخطوة 3 محدودة، انظر إلى الحالة بعد الخطوة 3:

الجذور النشطةخسارة كاملةالدرجة الجذرية
الحالة بعد حذف الحد الأدنى+R{\displaystyle +R}0{\displaystyle 0}+R+6{\displaystyle +R+6}
2×{\displaystyle 2\times }تدوير قائمة الانتظار0{\displaystyle 0}0{\displaystyle 0}+4{\displaystyle +4}
1×{\displaystyle 1\times }الحد من الخسائر+1{\displaystyle +1}-1{\displaystyle -1}+1{\displaystyle +1}
المجموع+R+1{\displaystyle +R+1}-1{\displaystyle -1}+R+11{\displaystyle +R+11}

لاحظ أن 3 عمليات تقليل للجذور النشطة وعمليات تقليل الجذور 2 تقلل من درجة الجذر والجذور النشطة بمقدار 1:

الجذور النشطةخسارة كاملةالدرجة الجذرية
3×{\displaystyle 3\times }تقليل الجذور النشط-3{\displaystyle -3}0{\displaystyle 0}+3{\displaystyle +3}
2×{\displaystyle 2\times }اختزال درجة الجذر+2{\displaystyle +2}0{\displaystyle 0}-4{\displaystyle -4}
المجموع-1{\displaystyle -1}0{\displaystyle 0}-1{\displaystyle -1}

منذR=2إل جي⁡ن+6{\displaystyle R=2\lg n+6}، الخطوة 3 لا تنفذ أبدًا أكثر منيا(سجل⁡ن){\displaystyle O(\log n)}مرات.

إثبات صحة النتائج

يتحقق الثابت 1 بشكل بديهي، حيث لا يتم إنشاء أي جذور فعالة.

حجم الكومةن{\displaystyle n}ينقص بمقدار واحد، مما يؤدي إلىR=2إل جي⁡ن+6{\displaystyle R=2\lg n+6}يتناقص بمقدار واحد على الأكثر. وبالتالي، فإن الثابت 3 لا يُنتهك إلا بمقدار واحد على الأكثر. وبحسب اللمة 3، فإن تقليل الخسارة ممكن، وقد تم ذلك في الخطوة 2.

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

لإثبات أن الشرط 5 مُحقق، نلاحظ أولاً أن حجم الكومةن{\displaystyle n}انخفضت بمقدار 1. لأن أول عقدتين فيسؤال{\displaystyle Q}يتم إزالة العناصر في الخطوة 1، ومواقع العناصر الأخرى فيسؤال{\displaystyle Q}تنخفض بمقدار 2. لذلك، قيود الدرجة2إل جي⁡(2ن-ص)+10{\displaystyle 2\lg(2n-p)+10}و2إل جي⁡(2ن-ص)+9{\displaystyle 2\lg(2n-p)+9}تبقى هذه العقد ثابتة. العقدتان اللتان تم إزالتهما سابقًا كانتا في الموضعين 1 و2 فيسؤال{\displaystyle Q}والآن يشغلون مناصبن-2{\displaystyle n-2}ون-1{\displaystyle n-1}على التوالي. والنتيجة هي أن قيود الدرجة الخاصة بهم قد تم تعزيزها بمقدار 2، ومع ذلك، قمنا بحذف اثنين من الأبناء السلبيين لكل من هذه العقد، وهو ما يكفي لتلبية القيد مرة أخرى.

مفتاح التناقص

يتم إنقاص مفتاح العقدة من 5 إلى 0. ثم يتم قطع الشجرة الفرعية وربطها بالجذر. وبما أن مفتاح الجذر هو 1، يتم تبديل المفاتيح.
عملية تقليل المفاتيح

يتركx{\displaystyle x}كن العقدة التي تم تقليل مفتاحها. إذاx{\displaystyle x}إذا كان هذا هو الجذر، فقد انتهينا. وإلا، فافصل الشجرة الفرعية التي جذرها عندx{\displaystyle x}، واربطه بالجذر. إذا كان مفتاحx{\displaystyle x}إذا كان المفتاح أصغر من مفتاح الجذر، فقم بتبديل مفاتيحهم.

قد يكون قد حدث ما يصل إلى ثلاثة انتهاكات هيكلية. ما لمx{\displaystyle x}إذا كان بالفعل ابنًا للجذر، فإن درجة الجذر تزداد بمقدار 1. عندماx{\displaystyle x}انفصل عن أصله الأصليy{\displaystyle y}لدينا الحالات التالية:

  • لوx{\displaystyle x}إذا كان الفعل سلبياً، فلا توجد انتهاكات إضافية.
  • لوx{\displaystyle x}كان سابقًا جذرًا نشطًا معy{\displaystyle y}سلبي، ثم متحركx{\displaystyle x}من كونه طفلاًy{\displaystyle y}لا يؤدي إنشاء فرع من الجذر إلى إنشاء أي جذور نشطة إضافية، كما أنه لا يزيد من فقدان أي عقدة.
  • إذا كان كلاهماx{\displaystyle x}وy{\displaystyle y}إذا كانت نشطة، فإن فقدانy{\displaystyle y}يزداد بمقدار 1، ويتم إنشاء جذر نشط إضافي (عن طريق الربط)x{\displaystyle x}(إلى الجذر).

في أسوأ الأحوال، تزداد جميع الكميات الثلاث (درجة الجذر، إجمالي الخسارة، الجذور النشطة) بمقدار 1.

بعد إجراء عملية تقليل الخسارة مرة واحدة، تظل أسوأ نتيجة هي زيادة درجة الجذر وعدد الجذور النشطة بمقدار 2. ولإصلاح هذه المخالفات، نستخدم حقيقة أن 3 عمليات تقليل للجذور النشطة وعمليتي تقليل للجذور تقللان كلتا الكميتين بمقدار 1. وبالتالي، فإن تطبيق هذه التحويلات 6 و4 مرات على التوالي يكفي للقضاء على جميع المخالفات.

الجذور النشطةخسارة كاملةالدرجة الجذرية
الحالة بعد مفتاح التناقص+1{\displaystyle +1}+1{\displaystyle +1}+1{\displaystyle +1}
1×{\displaystyle 1\times }الحد من الخسائر+1{\displaystyle +1}-1{\displaystyle -1}+1{\displaystyle +1}
6×{\displaystyle 6\times }تقليل الجذور النشط-6{\displaystyle -6}0{\displaystyle 0}+6{\displaystyle +6}
4×{\displaystyle 4\times }اختزال درجة الجذر+4{\displaystyle +4}0{\displaystyle 0}-8{\displaystyle -8}
المجموع0{\displaystyle 0}0{\displaystyle 0}0{\displaystyle 0}

إثبات صحة النتائج

العقد التي كانت سابقًا الأشقاء اليساريين لـx{\displaystyle x}التحرك لسد الفجوة التي خلفهاx{\displaystyle x}مما يؤدي إلى تقليل مؤشرها. وبما أن قيدها قد ضعف، فإن الثابت 1 لا يتأثر. ويتحقق الثابت 5 بشكل بديهي كما يلي:سؤال{\displaystyle Q}لم يتغير.

تضمن اللمات 2 و3 و4 إمكانية تقليل الجذر النشط، وتقليل الخسارة، وتقليل درجة الجذر. لذلك، فإن الثوابت 2 و3 و4 صحيحة.

أداء

على الرغم من كونها مثالية نظريًا، إلا أن أكوام فيبوناتشي الصارمة غير مفيدة في التطبيقات العملية. فهي معقدة للغاية في التنفيذ، وتتطلب إدارة أكثر من 10 مؤشرات لكل عقدة. [ 6 ] [ 7 ] بينما تُنفذ معظم العمليات فييا(1){\displaystyle O(1)}مع مرور الوقت، قد تكون العوامل الثابتة عالية جدًا، مما يجعلها أبطأ بما يصل إلى 20 مرة من نظيراتها الأكثر شيوعًا مثل أكوام البيانات الثنائية أو أكوام الاقتران . [ 8 ] على الرغم من بساطتها النسبية، تُظهر التجارب أن كومة فيبوناتشي الصارمة تعمل عمليًا بشكل أبطأ من طابور برودال. [ 9 ]

ملخص أوقات التشغيل

فيما يلي تعقيدات زمنية [ 10 ] لهياكل بيانات الكومة المختلفة. يشير الاختصار am. إلى أن التعقيد المذكور هو التعقيد المُستهلك، وإلا فهو تعقيد أسوأ حالة. لمعرفة معنى " O ( f )" و" Θ ( f )"، راجع ترميز Big O. تفترض أسماء العمليات وجود كومة دنيا.

عمليةالبحث عن الحد الأدنىحذف الحد الأدنىمفتاح التناقصأدخلاندماجmake-heap [ a ]
ثنائي [ 10 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )Θ ( n )
الانحراف [ 11 ]Θ (1)O (log n ) am. O (log n ) am. O (log n ) am. O (log n ) am. Θ ( n ) am.
يساري [ 12 ]Θ (1)Θ (log n ) Θ (log n ) Θ (log n ) Θ (log n ) Θ ( n )
ذات الحدين [ 10 ] [ 14 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1) صباحًا.Θ (log n ) [ b ] Θ ( n )
التوزيع الثنائي المائل [ 15 ]Θ (1)Θ (log n ) Θ (log n ) Θ (1)Θ (log n ) [ b ] Θ ( n )
2-3 كومة [ 17 ]Θ (1)O (log n ) am. Θ (1)Θ (1) صباحًا.O (log n ) [ b ] Θ ( n )
الانحراف من الأسفل إلى الأعلى [ 11 ]Θ (1)O (log n ) am. O (log n ) am. Θ (1) صباحًا.Θ (1) صباحًا.Θ ( n ) am.
الاقتران [ 18 ]Θ (1)O (log n ) am. o (log n ) am. [ c ] Θ (1)Θ (1)Θ ( n )
الاقتران بالرتب [ 21 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي [ 10 ] [ 22 ]Θ (1)O (log n ) am. Θ (1) صباحًا.Θ (1)Θ (1)Θ ( n )
فيبوناتشي الصارم [ 23 ] [ د ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n )
برودال [ 24 ] [ د ]Θ (1)Θ (log n ) Θ (1)Θ (1)Θ (1)Θ ( n ) [ 25 ]
  1. ↑ عملية بناء الكومة هي عملية إنشاء كومة من سلسلة من n عنصرًا غير مُرتبة. يمكن إنجازها فيزمن Θ ( n ) بينما تعمل خوارزمية دمج العناصر في زمن O (log n ) (حيث يمكن توزيع كلا التعقيدين). [ 11 ] [ 12 ] وتحقق خوارزمية أخرى زمن Θ ( n ) للكومات الثنائية. [ 13 ] 
  2. بالنسبة للأكوام المستمرة (التي لا تدعم تقليل المفتاح )، يُقلل تحويل عام تكلفة دمج العناصر إلى تكلفة إدراجها ، بينما تكون التكلفة الجديدة لحذف الحد الأدنى هي مجموع التكاليف القديمة لحذف الحد الأدنى ودمج العناصر . [ 16 ] هنا، يجعل هذا التحويل دمج العناصر يعمل في زمن Θ (1) (مُستهلك، إذا كانت تكلفة الإدراج كذلك)، بينما لا يزال حذف الحد الأدنى يعمل في زمن O (log n ). عند تطبيقه على أكوام ذات توزيع ثنائي منحرف، ينتج عنه طوابير برودال-أوكاساكي، وهي أكوام مستمرة ذات تعقيدات مثلى في أسوأ الحالات. [ 15 ] 
  3. ↑ الحد الأدنى لـΩ(سجل⁡سجل⁡ن)،{\displaystyle \Omega (\log \log n),}[ 19 ] الحد الأعلى لـيا(22سجل⁡سجل⁡ن).{\displaystyle O(2^{2{\sqrt {\log \log n}}}).}[ 20 ]
  4. تُحقق طوابير برودال وأكوام فيبوناتشي الصارمة أفضل تعقيد في أسوأ الحالات للأكوام. وقد وُصفت في البداية بأنها هياكل بيانات إجرائية. أما طابور برودال-أوكاساكي فهو هيكل بيانات مستمر يحقق نفس المستوى الأمثل، باستثناء أنهلا يدعم خاصية تقليل المفتاح .

مراجع

  1. ^ برودال، جيرث ستولتينج. لاجوجانيس، جورج. تارجان، روبرت إي. (2025). "أكوام فيبوناتشي الصارمة" . المعاملات ACM على الخوارزميات . 21 (2): 1– 18. دوى : 10.1145/3707692 .
  2. ↑ برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996). "قوائم الانتظار ذات الأولوية الوظيفية البحتة المثلى" . مجلة البرمجة الوظيفية . 6 (6): 839-857 . doi : 10.1017/S095679680000201X . ISSN 0956-7968 . 
  3. ↑ كنوت، دونالد إي. (24 أبريل 1998). فن برمجة الحاسوب: الفرز والبحث، المجلد 3. أديسون-ويسلي بروفيشنال. ISBN 978-0-321-63578-5.
  4. ↑ برودال، جيرث ستولتينغ (28 يناير 1996). "طوابير الأولوية الفعالة في أسوأ الحالات" . وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة . SODA '96. الولايات المتحدة الأمريكية: جمعية الرياضيات الصناعية والتطبيقية: 52-58 . ISBN 978-0-89871-366-4.
  5. ↑ فريدمان، مايكل ل.؛ تارجان، روبرت إندري (1987-07-01). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" . مجلة ACM . 34 (3): 596-615 . doi : 10.1145/28869.28874 . ISSN 0004-5411 . 
  6. 1 2 3 4 5 6 7 برودال، جيرث ستولتينغ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (19 مايو 2012). "أكوام فيبوناتشي الصارمة" . وقائع الندوة السنوية الرابعة والأربعين لجمعية آلات الحوسبة حول نظرية الحوسبة . STOC '12. نيويورك، نيويورك، الولايات المتحدة الأمريكية: جمعية آلات الحوسبة. الصفحات 1177-1184 . doi : 10.1145/2213977.2214082 . ISBN  978-1-4503-1245-5.
  7. ↑ ماجيريش، فلادان (25-11-2019)، أكوام فيبوناتشي السريعة مع امتدادات أسوأ الحالات ، arXiv : 1911.11637
  8. ↑ لاركين، دانيال؛ سين، سيدهارتا؛ تارجان، روبرت (2014). "دراسة تجريبية أساسية لقوائم الانتظار ذات الأولوية". وقائع ورشة العمل السادسة عشرة حول هندسة الخوارزميات والتجارب : 61-72 . arXiv : 1403.0252 . Bibcode : 2014arXiv1403.0252L . doi : 10.1137/1.9781611973198.7 . ISBN 978-1-61197-319-8. S2CID 15216766 . 
  9. ↑ مرينا، ميخال؛ سيدلاسيك، بيتر؛ كفاساي، ميروسلاف (يونيو 2019). "التطبيق العملي للتطبيقات المتقدمة لقوائم الانتظار ذات الأولوية في إيجاد أقصر المسارات". المؤتمر الدولي لتقنيات المعلومات والتقنيات الرقمية 2019 (IDT) . جيلينا، سلوفاكيا: IEEE. ص 335-344 . doi : 10.1109/DT.2019.8813457 . ISBN  9781728114019. S2CID 201812705 . 
  10. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  11. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  12. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  13. ↑ هايوارد، رايان؛ ماكديارميد، كولين (1991). "تحليل الحالة المتوسطة لبناء الكومة عن طريق الإدخال المتكرر" (ملف PDF) . مجلة الخوارزميات . 12 : 126-153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . مؤرشف من الأصل (ملف PDF) بتاريخ 2016-02-05 . تم الاطلاع عليه بتاريخ 2016-01-28 . 
  14. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  15. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  16. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  17. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  18. ↑ إياكونو، جون (2000)، "تحسين الحدود العليا لأكوام الاقتران"، وقائع ورشة العمل الإسكندنافية السابعة حول نظرية الخوارزميات (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1851، دار نشر سبرينغر، الصفحات 63-77 ، arXiv : 1110.4428 ، CiteSeerX 10.1.1.748.7812 ، doi : 10.1007/3-540-44985-X_5 ، ISBN    3-540-67690-2
  19. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  20. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  21. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  22. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  23. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  24. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  25. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.