كومة ذات الحدين

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

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

كومة ذات الحدين

يتم تنفيذ كومة ذات الحدين كمجموعة من الأشجار ذات الحدين (قارن مع كومة ثنائية ، والتي لها شكل شجرة ثنائية واحدة )، والتي يتم تعريفها بشكل متكرر على النحو التالي: [ 1 ]

  • الشجرة ذات الحدين من الرتبة 0 هي عقدة واحدة
  • شجرة ذات حدين من الرتبةك{\displaystyle k}يحتوي على عقدة جذرية تكون أبناؤها جذورًا لأشجار ذات حدين من رتبك-1{\displaystyle k-1}،ك-2{\displaystyle k-2}..., 2, 1, 0 (بهذا الترتيب).
الأشجار ذات الحدين من الرتبة 0 إلى 3: لكل شجرة عقدة جذرية تتفرع منها أشجار فرعية من جميع الأشجار ذات الحدين ذات الرتب الأدنى، والتي تم تمييزها. على سبيل المثال، ترتبط الشجرة ذات الحدين من الرتبة 3 بالأشجار ذات الحدين من الرتب 2 و1 و0 (المميزة باللون الأزرق والأخضر والأحمر على التوالي).

شجرة ذات حدين من الرتبةك{\displaystyle k}لديه2ك{\displaystyle 2^{k}}العقد، والارتفاعك{\displaystyle k}يأتي الاسم من الشكل: شجرة ذات حدين من الرتبةك{\displaystyle k}لديه(كد){\displaystyle {\tbinom {k}{d}}}العقد في العمقد{\displaystyle d}، معامل ذو حدين . وبسبب بنيته، فإن شجرة ذات حدين من الرتبةك{\displaystyle k}يمكن بناؤها من شجرتين من الرتبةك-1{\displaystyle k-1}عن طريق ربط أحدهما كأقصى فرع أيسر لجذر الشجرة الأخرى. تُعد هذه الخاصية أساسية لعملية دمج الكومة الثنائية، وهي ميزتها الرئيسية على الأكوام التقليدية الأخرى. [ 1 ] [ 3 ]

بنية كومة ذات حدين

يتم تنفيذ كومة ذات الحدين كمجموعة من الأشجار ذات الحدين التي تحقق خصائص كومة ذات الحدين : [ 1 ]

  • تخضع كل شجرة ذات الحدين في الكومة لخاصية الكومة الدنيا : مفتاح العقدة أكبر من أو يساوي مفتاح العقدة الأبوية.
  • يمكن أن يكون هناك شجرة ذات حدين واحدة على الأكثر لكل رتبة، بما في ذلك الرتبة الصفرية.

تضمن الخاصية الأولى أن جذر كل شجرة ذات حدين يحتوي على أصغر مفتاح في الشجرة. ويترتب على ذلك أن أصغر مفتاح في الكومة بأكملها هو أحد الجذور. [ 1 ]

الخاصية الثانية تعني أن كومة ذات حدين معن{\displaystyle n}تتكون العقد من عدد أقصى1+سجل2⁡ن{\displaystyle 1+\log _{2}n}الأشجار ذات الحدين، حيثسجل2{\displaystyle \log _{2}}هو اللوغاريتم الثنائي . يتم تحديد عدد وترتيب هذه الأشجار بشكل فريد من خلال عدد العقد.ن{\displaystyle n}يوجد شجرة ذات حدين واحدة لكل بت غير صفري في التمثيل الثنائي للعددن{\displaystyle n}على سبيل المثال، العدد العشري 13 هو 1101 في النظام الثنائي.23+22+20{\displaystyle 2^{3}+2^{2}+2^{0}}وبالتالي، فإن كومة ذات حدين تحتوي على 13 عقدة ستتألف من ثلاث أشجار ذات حدين من الرتب 3 و2 و0 (انظر الشكل أدناه). [ 1 ] [ 3 ]

مثال على كومة ذات حدين
مثال على كومة ثنائية تحتوي على 13 عقدة بمفاتيح مميزة. تتكون الكومة من ثلاث أشجار ثنائية برتب 0 و2 و3.

عدد الطرق المختلفة التين{\displaystyle n}يمكن ترتيب العناصر ذات المفاتيح المميزة في كومة ذات حدين تساوي أكبر قاسم فردي لـن!{\displaystyle n!}. لن=1،2،3،...{\displaystyle n=1,2,3,\dots }هذه الأرقام هي

1، 1، 3، 3، 15، 45، 315، 315، 2835، 14175، ... (التسلسل A049606 في OEIS )

إذان{\displaystyle n}يتم إدخال العناصر في كومة ذات حدين بترتيب عشوائي منتظم، وكل ترتيب من هذه الترتيبات له نفس الاحتمالية. [ 3 ]

تطبيق

لأن أي عملية لا تتطلب الوصول العشوائي إلى العقد الجذرية لأشجار ذات الحدين، يمكن تخزين جذور هذه الأشجار في قائمة مرتبطة ، مرتبة تصاعديًا حسب رتبة الشجرة. ولأن عدد الأبناء لكل عقدة متغير، فليس من العملي أن يكون لكل عقدة روابط منفصلة إلى كل ابن من أبنائها، كما هو شائع في الأشجار الثنائية ؛ بدلاً من ذلك، يمكن تمثيل هذه الشجرة باستخدام روابط من كل عقدة إلى ابنها الأعلى رتبة في الشجرة، وإلى شقيقها ذي الرتبة الأدنى التالية. يمكن تفسير مؤشرات الأشقاء هذه على أنها مؤشرات "التالي" في قائمة مرتبطة لأبناء كل عقدة، ولكن بترتيب معاكس لترتيب قائمة الجذور: من الأكبر إلى الأصغر، وليس العكس. يتيح هذا التمثيل ربط شجرتين من نفس الرتبة معًا، لتكوين شجرة من الرتبة الأعلى التالية، في وقت ثابت. [ 1 ] [ 3 ]

دمج

لدمج شجرتين ثنائيتين من نفس الرتبة، قارن أولًا مفتاح الجذر. بما أن 7 > 3، فإن الشجرة السوداء على اليسار (ذات العقدة الجذرية 7) تُلحق بالشجرة الرمادية على اليمين (ذات العقدة الجذرية 3) كشجرة فرعية. والنتيجة هي شجرة من الرتبة 3.

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

دالة دمج الشجرة (p، q) إذا كان مفتاح جذر p أصغر من أو يساوي مفتاح جذر q، تُرجع p.addSubTree(q) وإلا تُرجع q.addSubTree(p)
يوضح هذا دمج مجموعتين من الأشجار الثنائية. ويتم ذلك بدمج شجرتين ثنائيتين من نفس الرتبة واحدة تلو الأخرى. إذا كانت الشجرة المدمجة الناتجة من نفس رتبة إحدى الشجرتين الثنائيتين في إحدى المجموعتين، فسيتم دمج هاتين الشجرتين مرة أخرى.

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

دالة دمج (p، q) طالما لم يكن (p.end() و q.end()) tree = mergeTree(p.currentTree(), q.currentTree())
إذا لم تكن شجرة الكومة الحالية فارغة tree = mergeTree(tree, heap.currentTree())
 heap.addTree(tree) heap.next(); p.next(); q.next()

بما أن كل شجرة ذات حدين في كومة ذات حدين تُقابل بتًا في التمثيل الثنائي لحجمها، فهناك تشابه بين دمج كومتين وجمع حجميهما ثنائيًا ، من اليمين إلى اليسار. عندما يحدث حمل أثناء الجمع، فإن هذا يُقابله دمج شجرتين ذات حدين أثناء عملية الدمج. [ 1 ] [ 3 ]

لا تتضمن عملية اجتياز كل شجرة ذات الحدين أثناء الدمج سوى الجذور، مما يجعل الوقت المستغرق في أقصى حد من الرتبةسجل2⁡ن{\displaystyle \log _{2}n}وبالتالي فإن مدة التشغيل هييا(سجل⁡ن){\displaystyle O(\log n)}[ 1 ] [ 3 ]​

أدخل

يمكن إدراج عنصر جديد في كومة ببساطة عن طريق إنشاء كومة جديدة تحتوي على هذا العنصر فقط، ثم دمجها مع الكومة الأصلية. وبسبب عملية الدمج، تستغرق عملية الإدراج الواحدة وقتًا.يا(سجل⁡ن){\displaystyle O(\log n)}ومع ذلك، يمكن تسريع هذه العملية باستخدام إجراء دمج يختصر عملية الدمج بعد وصولها إلى نقطة تحتوي فيها كومة واحدة فقط من الكومات المدمجة على أشجار ذات رتبة أكبر. مع هذا التسريع، عبر سلسلة منك{\displaystyle k}في عمليات الإدخال المتتالية، يكون إجمالي وقت الإدخال هويا(ك+سجل⁡ن){\displaystyle O(k+\log n)}وبعبارة أخرى، (بعد احتساب التكلفة الإضافية اللوغاريتمية للإدخال الأول في التسلسل) فإن كل إدخال لاحق يستغرق وقتًا مستهلكًا قدرهيا(1){\displaystyle O(1)}(أي ثابت) لكل إدخال. [ 1 ] [ 3 ]

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

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

لإيجاد أصغر عنصر في الكومة، ابحث عن أصغر عنصر بين جذور الأشجار ذات الحدين. يمكن القيام بذلك فييا(سجل⁡ن){\displaystyle O(\log n)}الوقت، حيث لا يوجد سوىيا(سجل⁡ن){\displaystyle O(\log n)}جذور الأشجار لفحصها. [ 1 ]

باستخدام مؤشر إلى شجرة ذات الحدين التي تحتوي على العنصر الأدنى، يمكن تقليل وقت هذه العملية إلىيا(1){\displaystyle O(1)}يجب تحديث المؤشر عند إجراء أي عملية أخرى غير إيجاد القيمة الدنيا. ويمكن القيام بذلك فييا(سجل⁡ن){\displaystyle O(\log n)}الوقت لكل تحديث، دون زيادة وقت التشغيل التقاربي الإجمالي لأي عملية.

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

لحذف أصغر عنصر من الكومة، ابحث أولاً عن هذا العنصر، ثم أزله من جذر شجرته الثنائية، واحصل على قائمة بأشجاره الفرعية (التي هي بدورها أشجار ثنائية من رتب مختلفة). حوّل قائمة الأشجار الفرعية هذه إلى كومة ثنائية منفصلة بإعادة ترتيبها من الأصغر إلى الأكبر. ثم ادمج هذه الكومة مع الكومة الأصلية. بما أن كل جذر يحتوي على أكثر منسجل2⁡ن{\displaystyle \log _{2}n}يا أطفال، إن إنشاء هذه الكومة الجديدة يستغرق وقتاً.يا(سجل⁡ن){\displaystyle O(\log n)}يستغرق دمج الأكوام وقتًايا(سجل⁡ن){\displaystyle O(\log n)}لذا فإن عملية حذف الحد الأدنى بأكملها تستغرق وقتًايا(سجل⁡ن){\displaystyle O(\log n)}[ 1 ]​

دالة حذف أصغر عنصر في الكومة min = heap.trees().first() لكل شجرة حالية في heap.trees()، إذا كان جذر الشجرة الحالية أقل من جذر الشجرة الدنيا، فإن الشجرة الدنيا تساوي الشجرة الحالية. لكل شجرة فرعية في الشجرة الدنيا. tmp.addTree(tree) heap.removeTree(min) دمج (الكومة، مؤقت)

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

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

يمسح

لحذف عنصر من الكومة، قم بتقليل مفتاحه إلى سالب ما لا نهاية (أو بشكل مكافئ، إلى قيمة أقل من أي عنصر في الكومة) ثم احذف العنصر الأدنى في الكومة . [ 1 ]

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

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

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

التطبيقات

انظر أيضاً

  • الكومة الضعيفة ، وهي مزيج من بنيتي بيانات الكومة الثنائية والكومة ذات الحدين

مراجع

  1. ١ ٢ ٣ ٤ ٥ ٦ ٧ ٨ ٩ ١٠ ١١ ١٢ ١٣ ١٤ ١٥ ١٦ ١٧ كورمن، توماس هـ .؛ ليسرسون ، تشارلز إي.؛ ريفست ، رونالد ل.؛ شتاين ، كليفورد (٢٠٠١) [١٩٩٠]. "الفصل ١٩: أكوام ذات الحدين". مقدمة في الخوارزميات ( الطبعة الثانية). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. الصفحات ٤٥٥-٤٧٥ . ISBN   0-262-03293-7.
  2. ↑ فيليمين، جان (1 أبريل 1978). "بنية بيانات لمعالجة قوائم الانتظار ذات الأولوية" . اتصالات رابطة آلات الحوسبة . 21 (4): 309-315 . doi : 10.1145/359460.359478 .
  3. 1 2 3 4 5 6 7 8 9 10 براون، مارك ر. (1978). "تنفيذ وتحليل خوارزميات طابور ذي الحدين". مجلة SIAM للحوسبة . 7 (3): 298-319 . doi : 10.1137/0207026 . MR 0483830 . 
  4. ↑ برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  5. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  6. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  7. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  8. ↑ هايوارد، رايان؛ ماكديارميد، كولين (1991). "تحليل الحالة المتوسطة لبناء الكومة عن طريق الإدخال المتكرر" (ملف PDF) . مجلة الخوارزميات . 12 : 126-153 . CiteSeerX 10.1.1.353.7888 . doi : 10.1016/0196-6774(91)90027-v . مؤرشف من الأصل (ملف PDF) في 5 فبراير 2016. تم الاطلاع عليه في 28 يناير 2016 . 
  9. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30 سبتمبر 2019 .
  10. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  11. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  12. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  13. ↑ إياكونو، جون (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
  14. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  15. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  16. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  17. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  18. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  19. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  20. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.