طابور برودال

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

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

على الرغم من امتلاكها حدودًا تقاربية أفضل من هياكل قوائم الانتظار ذات الأولوية الأخرى، إلا أنها، على حد تعبير برودال نفسه، "معقدة للغاية" و"غير قابلة للتطبيق عمليًا". [ 1 ] يصف برودال وأوكاساكي نسخة مستمرة ( وظيفية بحتة ) من قوائم انتظار برودال. [ 2 ]

تعريف

طابور برودال هو مجموعة من شجرتينتي1{\displaystyle T_{1}}وتي2{\displaystyle T_{2}}وخمسة أدلة . يمكن الاطلاع على تعريف بنية بيانات الدليل في القسم التالي. بالنسبة لكلا الشجرتين، لكل عقدة رتبة ، وهذه الرتبة مفيدة للعمليات اللاحقة وتتوافق بشكل بديهي مع لوغاريتم حجم الشجرة الفرعية المتجذرة في العقدة. نلاحظرتبةأنا(x){\displaystyle {\text{arity}}_{i}(x)}عدد أبناء العقدةx{\displaystyle x}مع الرتبةأنا{\displaystyle i}سنستخدم أيضًات1{\displaystyle t_{1}}لجذر الشجرةتي1{\displaystyle T_{1}}وت2{\displaystyle t_{2}}لجذر الشجرةتي2{\displaystyle T_{2}}في كل لحظة معينة، يجب أن تستوفي كل شجرة فرعية متفرعة من عقدة ما هذه الثوابت الخمسة (والتي سيُطلق عليها لاحقًارتبة{\displaystyle {\text{RANK}}}الثوابت):

  • رتبة الورقة{\displaystyle {\text{LEAF-RANK}}} : لوx{\displaystyle x}إذا كانت ورقة شجر، فإذنرتبة(x)=0{\displaystyle {\text{rank}}(x)=0}،
  • الترتيب الأبوي{\displaystyle {\text{PARENT-RANK}}} :رتبة(x)<رتبة(أحد الوالدين(x)){\displaystyle {\text{rank}}(x)<{\text{rank}}({\text{parent}}(x))}،
  • المستوى التالي{\displaystyle {\text{NEXT-RANK-ARITY}}} : لورتبة(x)>0{\displaystyle {\text{rank}}(x)>0}، ثمرتبةرتبة(x)-1(x)⩾2{\displaystyle {\text{arity}}_{{\text{rank}}(x)-1}(x)\geqslant 2}،
  • مقيد بالفن{\displaystyle {\text{ARITY-BOUND}}}:رتبةأنا(x)∈{0،2،3،...،7}{\displaystyle {\text{arity}}_{i}(x)\in \{0,2,3,\dots ,7\}}نؤكد على ذلكرتبةأنا(x)≠1{\displaystyle {\text{arity}}_{i}(x)\neq 1}،
  • الترتيب الجذري{\displaystyle {\text{ROOT-RANK}}} :تي2=∅{\displaystyle T_{2}=\emptyset }أورتبة(ت1)⩽رتبة(ت2){\displaystyle {\text{rank}}(t_{1})\leqslant {\text{rank}}(t_{2})}.

هناالمستوى التالي{\displaystyle {\text{NEXT-RANK-ARITY}}}يضمن لنا ذلك أن حجم الشجرة الفرعية المتفرعة من عقدة ما يكون على الأقل أسيًا لرتبة تلك العقدة. بالإضافة إلى ذلك،مقيد بالفن{\displaystyle {\text{ARITY-BOUND}}}يحدد هذا عدد الأبناء من كل رتبة لعقدة معينة، وهذا يعني أن جميع العقد لها رتبة ودرجات فييا(سجل⁡ن){\displaystyle O(\log n)}.

في طابور برودال، لن تكون قيمة كل عقدة أكبر من قيمة عقدتها الأب، وتُسمى العقد التي تُخالف هذا الشرط بالعقد المخالفة . مع ذلك، نرغب في الحفاظ على عدد العقد المخالفة صغيرًا نسبيًا. لتتبع العقد المخالفة، نُنشئ مجموعتين لكل عقدة.V(x){\displaystyle V(x)}ودبليو(x){\displaystyle W(x)}من العقد الأكبر منx{\displaystyle x}بشكل بديهي،V(x){\displaystyle V(x)}هل العقد أكبر منx{\displaystyle x}برتبة عالية (بحيثy∈V(x){\displaystyle y\in V(x)}لورتبة(y)⩾رتبة(ت1){\displaystyle {\text{rank}}(y)\geqslant {\text{rank}}(t_{1})})، ودبليو(x){\displaystyle W(x)}هي العقد ذات الرتبة الصغيرة (رتبة(y)<رتبة(ت1){\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}تُنفَّذ هذه المجموعات باستخدام قائمة مرتبطة ثنائياً، مما يعني أنها مرتبة . وعلى وجه الخصوص، تُضاف جميع العقد المخالفة إلىV(x){\displaystyle V(x)}تُضاف في مقدمة القائمة، وتُضاف جميع العقد المخالفة إلىدبليو(x){\displaystyle W(x)}يتم إدراجها بجوار عقدة من نفس الرتبة. نسمحwأنا(x){\displaystyle w_{i}(x)}يشير إلى عدد العقد فيدبليو(x){\displaystyle W(x)}من الرتبةأنا{\displaystyle i}الV(x){\displaystyle V(x)}ودبليو(x){\displaystyle W(x)}تُحقق القوائم هذه الثوابت الخمسة (سنُسميهامجموعات{\displaystyle {\text{SETS}}}الثوابت):

  • الحد الأدنى للعقدة{\displaystyle {\text{MINIMUM-NODE}}} :ت1=مين(تي1∪تي2){\displaystyle t_{1}=\min(T_{1}\cup T_{2})}
  • مخالفة الشروط{\displaystyle {\text{انتهاك الشرط}}} : لوy∈V(x)∪دبليو(x){\displaystyle y\in V(x)\cup W(x)}ثمy⩾x{\displaystyle y\geqslant x}
  • مخالفة الوالدين{\displaystyle {\text{مخالفة للوالدين}}}: لوy<أحد الوالدين(y){\displaystyle y<{\text{parent}}(y)}ثم توجد عقدةx≠y{\displaystyle x\neq y}بحيثy∈V(x)∪دبليو(x){\displaystyle y\in V(x)\cup W(x)}
  • متأهل لمركز W{\displaystyle {\text{W-RANK-BOUND}}}:wأنا(x)⩽6{\displaystyle w_{i}(x)\leqslant 6}
  • مؤهل للحصول على رتبة V{\displaystyle {\text{مُؤهَّل للرتبة الخامسة}}}: عن طريق الإشارة إلىV(x)=(v|V(x)|،...،v2،v1){\displaystyle V(x)=(v_{|V(x)|},\dots ,v_{2},v_{1})}لدينا:رتبة(vأنا)⩾⌊أنا-1α⌋{\displaystyle {\text{rank}}(v_{i})\geqslant \left\lfloor {\frac {i-1}{\alpha }}\right\rfloor }لثابت معينα{\displaystyle \alpha }.

بما أن جميع العقد لها رتبة فييا(سجل⁡ن){\displaystyle O(\log n)}المتأهل لمركز W{\displaystyle {\text{W-RANK-BOUND}}}ومؤهل للحصول على رتبة V{\displaystyle {\text{مُؤهَّل للرتبة الخامسة}}}، الجميعV(x){\displaystyle V(x)}ودبليو(x){\displaystyle W(x)}هي بالحجميا(سجل⁡ن){\displaystyle O(\log n)}.

لدينا أيضًا بعض الثوابت لجذور الأشجارتي1{\displaystyle T_{1}}وتي2{\displaystyle T_{2}}:ت1{\displaystyle t_{1}}وت2{\displaystyle t_{2}}(يسمى)جذور{\displaystyle {\text{ROOTS}}}الثوابت).

  • الجذرية{\displaystyle {\text{ROOT-ARITY}}} :تأنا∈{2،3،...،7} ل أنا∈{0،1،...،رتبة(تأنا)-1}{\displaystyle t_{i}\in \{2,3,\dots ,7\}{\text{ for }}i\in \{0,1,\dots ,{\text{rank}}(t_{i})-1\}}،
  • مجلد بحجم V{\displaystyle {\text{V-SIZE-BOUND}}}:|V(x)|⩽α رتبة(ت1){\displaystyle |V(x)|\leqslant \alpha {\text{ rank}}(t_{1})}،
  • تصنيف العناصر W{\displaystyle {\text{W-ELEMENTS-RANK}}}: لوy∈دبليو(ت1){\displaystyle y\in W(t_{1})}، ثمرتبة(y)<رتبة(ت1){\displaystyle {\text{rank}}(y)<{\text{rank}}(t_{1})}.

المجلد بحجم V{\displaystyle {\text{V-SIZE-BOUND}}}يُخبرنا الثابت أساسًا أنه إذا قمنا بزيادة رتبةت1{\displaystyle t_{1}}واحد، لدينا على الأكثرα{\displaystyle \alpha }انتهاكات "كبيرة" جديدة (هنا تعني كلمة كبيرة امتلاك رتبة عالية) دون انتهاكمؤهل للحصول على رتبة V{\displaystyle {\text{مُؤهَّل للرتبة الخامسة}}}ثابت. من ناحية أخرى،تصنيف العناصر W{\displaystyle {\text{W-ELEMENTS-RANK}}}يخبرنا الثابت أن جميع الانتهاكات فيدبليو(x){\displaystyle W(x)}إذا كانت "صغيرة"، فإن هذا الشرط الثابت صحيح وفقًا لتعريفدبليو{\displaystyle W}الحفاظ على الثوابتمتأهل لمركز W{\displaystyle {\text{W-RANK-BOUND}}}والجذرية{\displaystyle {\text{ROOT-ARITY}}}الأمر ليس بسيطاً، وللحفاظ على هذه الأمور سنستخدممفتاح التناقص{\displaystyle {\text{DecreaseKey}}}عملية يمكن تنفيذها باستخدام دليل كما هو موضح في القسم التالي. في كل مرة سنستدعيمفتاح التناقص{\displaystyle {\text{DecreaseKey}}}في هذه العملية، سنقوم بشكل أساسي بما يلي  :

  1. أضف المخالفة الجديدة إلىV(ت1){\displaystyle V(t_{1})}أودبليو(ت1){\displaystyle W(t_{1})}وذلك بحسب درجة تلك المخالفة.
  2. لتجنبV(ت1){\displaystyle V(t_{1})}ودبليو(ت1){\displaystyle W(t_{1})}ولتجنب تضخمها بشكل مفرط، نقوم تدريجياً بنوعين من التحولات:
    1. نقل أبناءت2{\displaystyle t_{2}}لت1{\displaystyle t_{1}}لزيادة رتبةت1{\displaystyle t_{1}}
    2. تقليل عدد المخالفات فيدبليو(ت1){\displaystyle W(t_{1})}باستبدال انتهاكين للرتبةك{\displaystyle k}إلى انتهاك واحد للرتبةك+1{\displaystyle k+1}

بنية بيانات الدليل

يستند هذا التعريف إلى التعريف الوارد في ورقة برودال. [ 3 ]

نفترض أن لدينا سلسلة من المتغيراتxك،...،x1{\displaystyle x_{k},\dots ,x_{1}}ونريد التأكد من ذلك∀أنا⩽ك،xأنا⩽تي{\displaystyle \forall i\leqslant k,x_{i}\leqslant T}بالنسبة لعتبة معينةتي{\displaystyle T}العملية الوحيدة المسموح بها هييقلل(أنا){\displaystyle {\text{REDUCE}}(i)}مما يقللxأنا{\displaystyle x_{i}}بزيادة لا تقل عن 2 وتزيدxأنا+1{\displaystyle x_{i+1}}على الأكثر بمقدار 1. يمكننا أن نفترض دون فقدان للعمومية أنيقلل(أنا){\displaystyle {\text{REDUCE}}(i)}يقللxأنا{\displaystyle x_{i}}بمقدار 2 ويزدادxأنا+1{\displaystyle x_{i+1}}بواسطة 1.

إذا كانxج{\displaystyle x_{j}}إذا زاد بمقدار واحد، فإن هدف الدليل هو إخبارنا بالمؤشرات التي يتم استخدامها.أنا{\displaystyle i}للتقديميقلل(أنا){\displaystyle {\text{REDUCE}}(i)}وذلك احتراماً للحد الأدنى. يُسمح للمرشد فقط بـيا(1){\displaystyle O(1)}مكالمات إلىيقلل{\displaystyle {\text{REDUCE}}}دالة لكل زيادة.

يستطيع الدليل الوصول إلى تسلسل آخرxك′،...،x1′{\displaystyle x'_{k},\dots ,x'_{1}}بحيثxأنا⩽xأنا′{\displaystyle x_{i}\leqslant x'_{i}}وxأنا′∈{تي-2،تي-1،تي}{\displaystyle x'_{i}\in \{T-2,T-1,T\}}طالما بعد زيادةxج{\displaystyle x_{j}}لديناxج⩽xج′{\displaystyle x_{j}\leqslant x'_{j}}لسنا بحاجة إلى طلب المساعدة من مرشدنا السياحي لأنxج{\displaystyle x_{j}}هو "بعيد" أسفلتي{\displaystyle T}لكن، إذاxج=xج′{\displaystyle x_{j}=x'_{j}}قبل الزيادة، ثم لديناxج+1>xج′{\displaystyle x_{j}+1>x'_{j}}بعد التغيير.

لتبسيط الشرح، يمكننا أن نفترض أنتي=2{\displaystyle T=2}، لهذا السببxأنا′∈{0،1،2}{\displaystyle x'_{i}\in \{0,1,2\}}سيقوم الدليل بإنشاء كتل بالتسلسل التالي :xأنا′{\displaystyle x'_{i}}من الشكل2،1،1،...،1،0{\displaystyle 2,1,1,\dots ,1,0}حيث نسمح بعدم وجود1{\displaystyle 1}يُحافظ الدليل على الثابت القائل بأن كل عنصر ليس ضمن كتلة هو إما1{\displaystyle 1}أو0{\displaystyle 0}على سبيل المثال، إليك الكتل اللازمة لتسلسل منxأنا′{\displaystyle x'_{i}}.

1،2،1،1،0_،1،1،2،0_،2،0_،1،0،2،1،0_{\textstyle 1,{\underline {2,1,1,0}},1,1,{\underline {2,0}},{\underline {2,0}},1,0,{\underline {2,1,0}}}

يتكون الدليل من 3 مصفوفات  :

  • x{\displaystyle x}مصفوفة منxك،...،x1{\displaystyle x_{k},\dots ,x_{1}}
  • x′{\displaystyle x'}مصفوفة منxك′،...،x1′{\displaystyle x'_{k},\dots ,x'_{1}}
  • ص{\displaystyle p}مصفوفة من المؤشرات حيث جميعصأنا{\displaystyle p_{i}}والتيxأنا′{\displaystyle x'_{i}}إذا كانت القيم الموجودة في نفس الكتلة تشير إلى نفس خلية الذاكرة التي تحتوي على قيمة.xأنا′{\displaystyle x'_{i}}إذا لم يكن ضمن كتلة،صأنا{\displaystyle p_{i}}يشير إلى خلية ذاكرة تحتوي على⊥{\displaystyle \bot }.

وفقًا لهذا التعريف، يتمتع الدليل بخاصيتين مهمتين  :

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

وبهذه الطريقة، يستطيع الدليل تحديد المؤشرات التي يجبيقلل{\displaystyle {\text{REDUCE}}}في الوقت المناسبيا(1){\displaystyle O(1)}إليك مثال  :

2،1،1،0_،2،1،1،1،0_2،1،1،0_،2،2،1،1،0_زيادة xأنا′2،1،1،1_،0،2،1،1،0_يقلل2،1،1،1_،1،0،1،1،0_يقلل2،1،1،1،1،0_،1،1،0إعادة إنشاء الكتل{\displaystyle {\begin{array}{ll}{\underline {2,1,1,0}},{\underline {2,1,1,1,0}}&\\{\underline {2,1,1,0}},{\underline {2,{\color {red}2},1,1,0}}&{\text{Increment }}x'_{i}\\{\underline {2,1,1,{\color {green}1}}},{\underline {{\color {blue}0},2,1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1}},{\underline {{\color {green}1},{\color {blue}0},1,1,0}}&{\text{REDUCE}}\\{\underline {2,1,1,1,1,0}},1,1,0&{\text{reestablish blocks}}\\\end{array}}}

لإعادة إنشاء الكتل، تشير مؤشرات 1 و0 المضافة إلى الكتلة الأولى الآن إلى نفس الخلية التي تشير إليها جميع العناصر الأخرى من الكتلة الأولى، ويتم تغيير قيمة خلية الكتلة الثانية إلى⊥{\displaystyle \bot }في المثال السابق، اثنان فقطيقلل{\displaystyle {\text{REDUCE}}}كانت هناك حاجة إلى عمليات، وهذا هو الحال في جميع الحالات. لذلك، لا يحتاج الطابور إلا إلىيا(1){\displaystyle O(1)}عمليات لإعادة تأسيس العقار.

عمليات طابور برودال

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

التحولات

ربط الأشجار

لربط الأشجار، نحتاج إلى ثلاث عقدx1،x2 و x3{\displaystyle x_{1},x_{2}{\text{ and }}x_{3}}ذات رتبة متساوية. يمكننا حساب الحد الأدنى لهذه العقد الثلاث بمقارنتين. نفترض هنا أنx1{\displaystyle x_{1}}هذا هو الحد الأدنى، لكن العملية متشابهة للجميع.xأنا{\displaystyle x_{i}}يمكننا الآن إنشاء العقدx2{\displaystyle x_{2}}وx3{\displaystyle x_{3}}الابنان الأيسران لـx1{\displaystyle x_{1}}ورفع رتبةx1{\displaystyle x_{1}}واحداً تلو الآخر. وهذا يحافظ على كل شيءرتبة{\displaystyle {\text{RANK}}}ومجموعات{\displaystyle {\text{SETS}}}الثوابت.

فصل الأشجار

لوx{\displaystyle x}لديه بالضبط اثنين أو ثلاثة أبناء من ذوي المكانة الرفيعةرتبة(x)-1{\displaystyle {\text{rank}}(x)-1}يمكننا إزالة هؤلاء الأبناء وx{\displaystyle x}يحصل على رتبة أكبر أبنائه الجدد بالإضافة إلى واحد. منمقيد بالفن{\displaystyle {\text{ARITY-BOUND}}}في هذه الحالة، نعلم أنالمستوى التالي{\displaystyle {\text{NEXT-RANK-ARITY}}}سيتم الحفاظ على الثابت. بعد ذلك، كلرتبة{\displaystyle {\text{RANK}}}ومجموعات{\displaystyle {\text{SETS}}}تبقى الثوابت مُحققة. إذاx{\displaystyle x}إذا كان للشجرة أربعة أبناء أو أكثر، فيمكننا ببساطة حذف اثنين منهم وتبقى جميع الثوابت صحيحة. لذلك، فإن فصل شجرة من الرتبةك{\displaystyle k}سيؤدي ذلك دائمًا إلى شجرتين أو ثلاث شجرات من الرتبةك-1{\displaystyle k-1}(من بين الطفلين أو الثلاثة الذين تم استبعادهم) وشجرة إضافية واحدة من الرتبة على الأكثرك{\displaystyle k}.

الحفاظ على أبناء الجذر

عندما نضيف ونزيل أبناء الجذر، فإننا نريد الاحتفاظ بـالترتيب الجذري{\displaystyle {\text{ROOT-RANK}}}صحيح وثابت. لهذا الغرض، نستخدم 4 أدلة، اثنان لكل جذر.ت1{\displaystyle t_{1}}وت2{\displaystyle t_{2}}. أن يكون لديه إمكانية الوصول المستمر إلى ابنت1{\displaystyle t_{1}}نقوم بإنشاء مصفوفة قابلة للتوسيع من المؤشرات تحتوي على لكل رتبةأنا∈{0،...،رتبة(ت1)-1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}دليل إلى ابنت1{\displaystyle t_{1}}من الرتبةأنا{\displaystyle i}سيحافظ أحد المرشدين على الشرط الذيرتبةأنا(ت1)⩽7{\displaystyle {\text{arity}}_{i}(t_{1})\leqslant 7}والآخر يؤكدرتبةأنا(ت1)⩾2{\displaystyle {\text{arity}}_{i}(t_{1})\geqslant 2}كلاهما لـأنا∈{0،...،رتبة(ت1)-3}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-3\}}أبناءت1{\displaystyle t_{1}}من رتبةرتبة(ت1)-1{\displaystyle {\text{rank}}(t_{1})-1}ورتبة(ت1)-2{\displaystyle {\text{rank}}(t_{1})-2}تُعامل بشكل منفصل وبطريقة مباشرة للحفاظ على عددها بين 2 و7. وهو ما يعادلxأنا′{\displaystyle x'_{i}}سيحتوي المتغير في تعريف الدليل على القيم التالية{5،6،7}{\displaystyle \{5,6,7\}}للحصول على دليل الحد الأعلى و{4،3،2}{\displaystyle \{4,3,2\}}للحد الأدنى.

في هذا السياق، عندما نضيف طفلاً من رتبةأنا{\displaystyle i}إلى الجذر، نزيدxأنا′{\displaystyle x'_{i}}واحداً تلو الآخر، ثم قم بتطبيقيقلل{\displaystyle {\text{REDUCE}}}العمليات. الـإنقاذ(أنا){\displaystyle {\text{RECUCE}}(i)}تتألف العملية هنا من ربط ثلاث أشجار من الرتبةأنا{\displaystyle i}مما يؤدي إلى إنشاء طفل جديد من الرتبةأنا+1{\displaystyle i+1}لذلك، نقوم بتقليلرتبةأنا(ت1){\displaystyle {\text{arity}}_{i}(t_{1})}بمقدار ثلاثة وزيادةرتبةأنا+1(ت1){\displaystyle {\text{arity}}_{i+1}(t_{1})}بواحد. إذا أدت هذه الزيادة إلى وجود عدد كبير جدًا من أبناء الطبقة العليارتبة(ت1)-2{\displaystyle {\text{rank}}(t_{1})-2}أورتبة(ت1)-1{\displaystyle {\text{rank}}(t_{1})-1}نربط بعض هؤلاء الأبناء ببعضهم البعض، وربما نرفع من رتبةت1{\displaystyle t_{1}}إذا قمنا بزيادة رتبةت1{\displaystyle t_{1}}، علينا زيادة طول المصفوفة القابلة للتمديد التي تديرها الأدلة.

قطع العلاقة بين الابن وت1{\displaystyle t_{1}}متشابهة جدًا، باستثناء هنا...يقلل{\displaystyle {\text{REDUCE}}}تتوافق هذه العملية مع عملية فصل الشجرة.

للجذرت2{\displaystyle t_{2}}الوضع يكاد يكون متشابهاً. ومع ذلك، بما أنالحد الأدنى للعقدة{\displaystyle {\text{MINIMUM-NODE}}}يضمن لنا ذلكت1{\displaystyle t_{1}}بما أن العنصر هو الحد الأدنى، فإننا نعلم أننا لن نخلق أي انتهاك من خلال ربط أو فصل العناصر الفرعية لـت1{\displaystyle t_{1}}لا ينطبق الأمر نفسه علىت2{\displaystyle t_{2}}ربط الأبناء لا يُنشئ انتهاكات جديدة، لكن فصل الأبناء قد يُنشئ ما يصل إلى ثلاثة انتهاكات جديدة. الشجرة المتبقية بعد الفصل تُصبح ابنًا لـت1{\displaystyle t_{1}}إذا كان ترتيبه أقل منرتبة(ت1){\displaystyle {\text{rank}}(t_{1})}وإلا فإنه يصبح ابنًا لـت2{\displaystyle t_{2}}الانتهاكات الجديدة التي احتلت مرتبة أعلى منرتبة(ت1){\displaystyle {\text{rank}}(t_{1})}تُضاف إلىV(ت1){\displaystyle V(t_{1})}للحفاظ على الثوابت علىV(ت1){\displaystyle V(t_{1})}مجموعة (أيمؤهل للحصول على رتبة V{\displaystyle {\text{V-RANK-BOUND}}}ومجلد بحجم V{\displaystyle {\text{V-SIZE-BOUND}}}علينا أن نضمن أن رتبةت1{\displaystyle t_{1}}سيتم زيادتها، وذلكα{\displaystyle \alpha }يتم اختيار هذه الثوابت كبيرة بما يكفي.

الحد من المخالفات

يهدف هذا التحول إلى تقليل إجمالي عدد الانتهاكات المحتملة، أي تقليل|⋃x∈تي1∪تي2V(x)∪دبليو(x)|{\displaystyle \left|\bigcup _{x\in T_{1}\cup T_{2}}V(x)\cup W(x)\right|}.

نفترض أن لدينا انتهاكين محتملينx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}من نفس الرتبةك{\displaystyle k}ثم لدينا عدة حالات:

  1. إذا تبين أن إحدى العقد لا تشكل انتهاكًا، فإننا ببساطة نزيلها من مجموعة الانتهاكات المقابلة لها.
  2. وإلا، فإن كلا العقدتين تُعتبران مخالفتين. بسببمقيد بالفن{\displaystyle {\text{ARITY-BOUND}}}نعلم أن كلاx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}أن يكون لديك أخ واحد على الأقل. ثم:
    1. لوx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}إذا لم يكونوا إخوة، فيمكننا أن نفترض دون فقدان العمومية أنأحد الوالدين(x1)⩽أحد الوالدين(x2){\displaystyle {\text{parent}}(x_{1})\leqslant {\text{parent}}(x_{2})}ثم يمكننا تبديل الأشجار الفرعية المتجذرة فيx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}لا يمكن أن ينخفض ​​عدد المخالفات إلا خلال عملية التبديل هذه.
    2. آخر،x1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}هم إخوة لعقدة سنسميهاy{\displaystyle y}.
      1. لوx1{\displaystyle x_{1}}له أكثر من أخ واحد من ذوي الرتب العاليةك{\displaystyle k}يمكننا ببساطة قطع الاتصالx1{\displaystyle x_{1}}واجعلها عقدة غير منتهكة لـت1{\displaystyle t_{1}}كما هو موضح في القسم الفرعي السابق.
      2. آخر،x1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}هم الأبناء الوحيدون ذوو المكانةك{\displaystyle k}لy{\displaystyle y}..
        1. لورتبة(y)>ك+1{\displaystyle {\text{rank}}(y)>k+1}يمكننا قطع كليهماx1{\displaystyle x_{1}}وx2{\displaystyle x_{2}}العقد منy{\displaystyle y}واجعلها عقدًا غير منتهكة لـت1{\displaystyle t_{1}}كما هو موضح في القسم الفرعي السابق
        2. آخر،رتبة(y)=ك+1{\displaystyle {\text{rank}}(y)=k+1}سنقطع الاتصالx1،x2 و y{\displaystyle x_{1},x_{2}{\text{ and }}y}، الرتبة الجديدة لـy{\displaystyle y}سيكون واحدًا زائد رتبة ابنه الأيسر، نستبدلy{\displaystyle y}بواسطة ابن فيت1{\displaystyle t_{1}}من الرتبةك+1{\displaystyle k+1}والتي يمكن قطعها كما هو موضح في القسم الفرعي السابق. إذا كان البديل لـy{\displaystyle y}يصبح عقدة منتهكة للرتبةك+1{\displaystyle k+1}نضيفه إلىدبليو(ت1){\displaystyle W(t_{1})}وأخيراً نقوم بـx1،x2 و y{\displaystyle x_{1},x_{2}{\text{ and }}y}أبناء جددت1{\displaystyle t_{1}}كما هو موضح أعلاه.

تجنب الكثير من الانتهاكات

مجموعات المخالفات الوحيدة التي سنضيف إليها مخالفات هيV(ت1){\displaystyle V(t_{1})}ودبليو(ت1){\displaystyle W(t_{1})}كما هو موضح أعلاه، يتم الحفاظ على الثوابت في تلك المجموعات باستخدام أدلة. عندما نضيف انتهاكًا إلىدبليو(ت1){\displaystyle W(t_{1})}لدينا حالتان:

  1. إذا كان هناك ستة انتهاكات بالضبط من الرتبة المحددة، وكان هناك عقدتان منتهكتان على الأقل ليستا من أبناءت2{\displaystyle t_{2}}، نطبقيقلل{\displaystyle {\text{REDUCE}}}العمليات المذكورة في الدليل.
  2. إذا كان هناك أكثر من 4 انتهاكات، فإن أبناءت2{\displaystyle t_{2}}قمنا بحذف المخالفات الإضافية ووضعنا روابطها أدناه.ت1{\displaystyle t_{1}}هذا يزيل المخالفة التي أنشأتها هذه العقد ولا يؤثر على الدليل الذي يحافظ على أبناءت2{\displaystyle t_{2}}.

لكل عملية يتم تنفيذها في قائمة الانتظار ذات الأولوية، نقوم بزيادة رتبةت1{\displaystyle t_{1}}بواحد على الأقل عن طريق تحريك عدد ثابت من أبناءت2{\displaystyle t_{2}}لت1{\displaystyle t_{1}}(شريطة أنتي2≠∅{\displaystyle T_{2}\neq \emptyset }زيادة رتبةت1{\displaystyle t_{1}}يسمح لنا بإضافة المخالفات إلىV(ت1){\displaystyle V(t_{1})}مع الحفاظ على جميع ثوابتنا. إذاتي2≠∅{\displaystyle T_{2}\neq \emptyset }ورتبة(ت2)⩽رتبة(ت1)+2{\displaystyle {\text{rank}}(t_{2})\leqslant {\text{rank}}(t_{1})+2}يمكننا أن نقطع أكبر أبناءت2{\displaystyle t_{2}}، قم بربطها بـت1{\displaystyle t_{1}}ثم اصنعت2{\displaystyle t_{2}}ابنت1{\displaystyle t_{1}}وهذا يحقق جميع الشروط. وإلا، فإننا نقطع ابنًا لـت2{\displaystyle t_{2}}من الرتبةرتبة(ت1)+2{\displaystyle {\text{rank}}(t_{1})+2}افصل هذا الابن وأضف الأشجار الناتجة إلىت1{\displaystyle t_{1}}. لوتي2=∅{\displaystyle T_{2}=\emptyset }نعلم أنت1{\displaystyle t_{1}}هي العقدة ذات الرتبة الأكبر، لذلك نعلم أنه لا يمكن إنشاء انتهاكات كبيرة.

عمليات قائمة الانتظار ذات الأولوية

إنشاء قائمة الانتظار

إنشاء قائمة الانتظار(){\displaystyle {\text{MakeQueue}}()}لا يُعيد سوى شجرتين فارغتين.

فايند مين

فايند مين(سؤال){\displaystyle {\text{FindMin}}(Q)}عمليات الإرجاعت1{\displaystyle t_{1}}.

أدخل

أدخل(سؤال،هـ){\displaystyle {\text{Insert}}(Q,e)}إنها مجرد حالة خاصة مناندماج(سؤال1،سؤال2){\displaystyle {\text{Meld}}(Q_{1},Q_{2})}أينسؤال2{\displaystyle Q_{2}}هي قائمة انتظار تحتوي فقط علىهـ{\displaystyle e}وسؤال1=سؤال{\displaystyle Q_{1}=Q}.

اندماج

اندماج(سؤال1،سؤال2){\displaystyle {\text{Meld}}(Q_{1},Q_{2})}يتضمن ذلك أربع أشجار (اثنتان لكل طابور). الشجرة التي لها أصغر جذر تصبح هي الجديدةتي1{\displaystyle T_{1}}إذا كانت هذه الشجرة هي أيضًا الشجرة ذات الرتبة القصوى، فيمكننا إضافة جميع الأشجار الأخرى أدناه كما هو موضح سابقًا. في هذه الحالة، لا يتم إنشاء أي عقدة مخالفة، وبالتالي لا يتم إجراء أي تحويل على العقد المخالفة. وإلا، تصبح الشجرة ذات الرتبة القصوى هي الشجرة الجديدة.تي2{\displaystyle T_{2}}تُضاف الشجرة والأشجار الأخرى أدناه كما هو موضح في قسم "الحفاظ على أبناء الجذر". إذا كانت بعض الأشجار لها نفس رتبة هذه الشجرة الجديدةتي2{\displaystyle T_{2}}يمكننا فصلها قبل إضافتها. ويتم التعامل مع المخالفات الناتجة كما هو موضح في قسم  "تجنب كثرة المخالفات".

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

مفتاح التناقص(سؤال،هـ،هـ′){\displaystyle {\text{DecreaseKey}}(Q,e,e')}يستبدل عنصرهـ{\displaystyle e}بواسطةهـ′{\displaystyle e'}(معهـ′⩽هـ{\displaystyle e'\leqslant e}). لوهـ′<ت1{\displaystyle e'<t_{1}}، نقوم بتبديل العقدتين، وإلا فإننا نتعامل مع الانتهاك الجديد المحتمل كما هو موضح في قسم "تجنب الكثير من الانتهاكات".

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

حذف الحد الأدنى(سؤال){\displaystyle {\text{DeleteMin}}(Q)}يُسمح له بأخذ أسوأ وقت ممكنيا(سجل⁡ن){\displaystyle O(\log n)}أولاً، نقوم بتفريغها بالكاملتي2{\displaystyle T_{2}}بنقل جميع أبناءت2{\displaystyle t_{2}}لت1{\displaystyle t_{1}}ثم اصنعت2{\displaystyle t_{2}}ابن من الرتبة صفرت1{\displaystyle t_{1}}. ثم،ت1{\displaystyle t_{1}}يتم حذفه، وهذا يترك لنا على الأكثريا(سجل⁡ن){\displaystyle O(\log n)}الأشجار المستقلة. ثم يتم إيجاد الحد الأدنى الجديد من خلال النظر إلى المجموعات المخالفة للجذر القديم والنظر إلى جميع جذور الأشجار الجديدة. إذا لم يكن العنصر الأدنى جذرًا، فيمكننا استبدال جذر من شجرة من نفس الرتبة به. هذا يُنشئ انتهاكًا واحدًا على الأكثر. بعد ذلك، نجعل الأشجار المستقلة أبناءً للعنصر الأدنى الجديد من خلال تنفيذيا(سجل⁡ن){\displaystyle O(\log n)}عمليات الربط وفك الربط. وهذا يعيد إنشاءرتبة{\displaystyle {\text{RANK}}}وجذور{\displaystyle {\text{ROOTS}}}الثوابت. من خلال دمجV{\displaystyle V}ودبليو{\displaystyle W}مجموعات الجذر الجديد بالإضافة إلىV{\displaystyle V}ودبليو{\displaystyle W}مجموعات الجذر القديم معًا، نحصل على مجموعة انتهاكات جديدة واحدة بحجميا(سجل⁡ن){\displaystyle O(\log n)}عن طريق القيام على الأكثريا(سجل⁡ن){\displaystyle O(\log n)}من خلال التحويلات التي تقلل من الانتهاكات، يمكننا جعل مجموعة الانتهاكات تحتوي على عنصر واحد على الأكثر من كل رتبة. ستكون هذه المجموعة هي مجموعتنا الجديدة.دبليو{\displaystyle W}مجموعة والجديدV{\displaystyle V}المجموعة فارغة. هذا يعيد إنشاءمجموعات{\displaystyle {\text{SETS}}}الثوابت. علينا أيضًا تهيئة دليل جديد للجذر الجديدت1{\displaystyle t_{1}}.

يمسح

هنا،-∞{\displaystyle -\infty }يشير إلى أصغر عنصر ممكن.يمسح(سؤال،هـ){\displaystyle {\text{Delete}}(Q,e)}يمكن تنفيذ ذلك ببساطة عن طريق استدعاءمفتاح التناقص(سؤال،هـ،-∞){\displaystyle {\text{DecreaseKey}}(Q,e,-\infty )}ثم يتبع ذلكحذف الحد الأدنى(سؤال){\displaystyle {\text{DeleteMin}}(Q)}.

تفاصيل التنفيذ

في هذا القسم، نلخص بعض تفاصيل التنفيذ لهيكل بيانات قائمة انتظار برودال.

في كل شجرة، كل عقدة عبارة عن سجل يحتوي على الحقول التالية:

  • العنصر المرتبط بالعقدة (قيمته)،
  • رتبة العقدة،
  • مؤشرات إلى العقدة الشقيقة اليسرى واليمنى،
  • مؤشر إلى العقدة الأب،
  • مؤشر إلى الابن الأيسر،
  • مؤشرات إلى العنصر الأول من العقدةV{\displaystyle V}ودبليو{\displaystyle W}مجموعات،
  • مؤشرات إلى العنصر التالي والعنصر السابق في مجموعة المخالفات التي ينتمي إليها العقدة. إذا كانت هذه العقدة هي العقدة الأولى في مجموعة المخالفاتV(x){\displaystyle V(x)}أودبليو(x){\displaystyle W(x)}ينتمي إلى، يشير المؤشر السابق إلىx{\displaystyle x}.
  • مجموعة من المؤشرات لأبناءت1{\displaystyle t_{1}}من الرتبةأنا{\displaystyle i}(معأنا∈{0،...،رتبة(ت1)-1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}})
  • مصفوفة مماثلة لـت2{\displaystyle t_{2}}،
  • مصفوفة من المؤشرات إلى العقد فيدبليو(ت1){\displaystyle W(t_{1})}من الرتبةأنا{\displaystyle i}(معأنا∈{0،...،رتبة(ت1)-1}{\displaystyle i\in \{0,\dots ,{\text{rank}}(t_{1})-1\}}).

وأخيرًا، لدينا 5 أدلة: ثلاثة للحفاظ على الحدود العليا لـرتبةأنا(ت1){\displaystyle {\text{arity}}_{i}(t_{1})}،رتبةأنا(ت2){\displaystyle {\text{arity}}_{i}(t_{2})}وwأنا(ت1){\displaystyle w_{i}(t_{1})}واثنين للحفاظ على الحدود الدنيا لـرتبةأنا(ت1){\displaystyle {\text{arity}}_{i}(t_{1})}ورتبةأنا(ت2){\displaystyle {\text{arity}}_{i}(t_{2})}.

نظرًا لكثرة المؤشرات والمجموعات التي يجب تتبعها، يُعدّ تنفيذ طابور برودال أمرًا بالغ الصعوبة. ولهذا السبب، يُوصف بأنه كائن نظري بحت يهدف إلى تقليل التعقيد الزمني في خوارزميات مثل خوارزمية ديكسترا . مع ذلك، تمّ تنفيذ طابور برودال بلغة سكالا ( يمكن العثور على مستودع GitHub هنا: https://github.com/ruippeixotog/functional-brodal-queues ). في ورقته البحثية، يذكر جيرث ستولتينغ برودال أن: "من القضايا المهمة التي تتطلب مزيدًا من العمل تبسيط البنية لجعلها قابلة للتطبيق عمليًا". [ 3 ]

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

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

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

جيرث ستولتينغ برودال

جيرث ستولتينج برودال أستاذ بجامعة آرهوس بالدنمارك . [ 20 ] اشتهر بقائمة انتظار برودال.

مراجع

  1. 1 2 جيرث ستولتينغ برودال (1996). قوائم الانتظار ذات الأولوية الفعالة في أسوأ الحالات. وقائع الندوة السابعة لجمعية آلات الحوسبة وجمعية الرياضيات التطبيقية والصناعية حول الخوارزميات المنفصلة، ​​الصفحات 52-58
  2. ↑ جيرث ستولتينغ برودال وكريس أوكاساكي (1996). قوائم الانتظار ذات الأولوية الوظيفية البحتة المثلى . مجلة البرمجة الوظيفية.
  3. 1 2 برودال، جيرث ستولتينج (1996). “قوائم الانتظار ذات الأولوية ذات الكفاءة الأسوأ” (PDF) .{{cite web}}: CS1 maint: url-status ( link )
  4. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  5. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  6. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  7. ↑ هايوارد، رايان؛ ماكديارميد، كولين (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 . 
  8. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  9. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  10. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  11. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  12. ↑ إياكونو، جون (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
  13. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  14. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  15. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  16. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  17. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  18. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  19. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.
  20. ^ "الموقع الإلكتروني لجيرث ستولتينج برودال، في جامعة آرهوس" . تم الاسترجاع 18 فبراير 2016 .