الكومة (هيكل البيانات)

📅 آخر تحديث: ٢٣ يوليو ٢٠٢٦
✍️ نُشر في: ٢٣ يوليو ٢٠٢٦
📷 يحتوي على 13 صور
الموسوعة الحرة
مثال على كومة ثنائية قصوى بمفاتيح عقدية عبارة عن أعداد صحيحة بين 1 و 100

في علم الحاسوب ، الكومة هي بنية بيانات شجرية تحقق خاصية الكومة : في الكومة العظمى ، لأي عقدة معينة C، إذا كانت P هي العقدة الأب لـ C، فإن مفتاح ( قيمة ) P يكون أكبر من أو يساوي مفتاح C. في الكومة الصغرى ، يكون مفتاح P أصغر من أو يساوي مفتاح C. [ 1 ] تُسمى العقدة الموجودة في "قمة" الكومة (بدون آباء) بالعقدة الجذرية .

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

يُعدّ الكومة الثنائية أحد التطبيقات الشائعة للكومة ، حيث تكون الشجرة فيها شجرة ثنائية كاملة [ 2 ] (انظر الشكل). وقد قدّم جيه دبليو جيه ويليامز بنية بيانات الكومة، وتحديدًا الكومة الثنائية، عام 1964، كبنية بيانات لخوارزمية فرز الكومة . [ 3 ] كما تُعدّ الكومات أساسية في العديد من خوارزميات الرسوم البيانية الفعّالة ، مثل خوارزمية ديكسترا . عندما تكون الكومة شجرة ثنائية كاملة، يكون لها أصغر ارتفاع ممكن - فالكومة التي تحتوي على N عقدة و a فرعًا لكل عقدة يكون ارتفاعها دائمًا log N.

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

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

العمليات

العمليات الشائعة التي تتضمن الأكوام هي:

أساسي
  • دالة البحث عن الحد الأقصى (أو البحث عن الحد الأدنى ): إيجاد عنصر أقصى في كومة الحد الأقصى، أو عنصر أدنى في كومة الحد الأدنى، على التوالي (وتُعرف أيضًا باسم المعاينة ).
  • إدراج : إضافة مفتاح جديد إلى الكومة (أي دفع [ 4 ] )
  • extract-max (أو extract-min ): تُعيد العقدة ذات القيمة القصوى من كومة قصوى [أو القيمة الدنيا من كومة دنيا] بعد إزالتها من الكومة (أي pop [ 5 ] ).
  • حذف الحد الأقصى (أو حذف الحد الأدنى ): إزالة العقدة الجذرية من كومة الحد الأقصى (أو كومة الحد الأدنى)، على التوالي
  • استبدال : قم بإزالة المفتاح الجذر ودفع مفتاح جديد. هذه الطريقة أكثر كفاءة من عملية الإزالة متبوعة بالدفع، لأنها تحتاج إلى موازنة البيانات مرة واحدة فقط، وليس مرتين، وهي مناسبة للأكوام ذات الحجم الثابت. [ 6 ]
الخلق
  • إنشاء كومة : إنشاء كومة فارغة
  • heapify : إنشاء كومة من مصفوفة عناصر معينة
  • دمج ( اتحاد ): ضم كومتين لتشكيل كومة جديدة صالحة تحتوي على جميع عناصر كليهما، مع الحفاظ على الكومتين الأصليتين.
  • الدمج : ضم كومتين لتشكيل كومة جديدة صالحة تحتوي على جميع عناصر كليهما، مما يؤدي إلى تدمير الكومات الأصلية.
تقتيش
  • الحجم : إرجاع عدد العناصر في الكومة.
  • is-empty : تُرجع القيمة true إذا كانت الكومة فارغة، و false خلاف ذلك.
داخلي
  • زيادة المفتاح أو إنقاص المفتاح : تحديث مفتاح داخل كومة قصوى أو كومة دنيا، على التوالي
  • حذف : حذف عقدة عشوائية (متبوعًا بنقل العقدة الأخيرة والفرز للحفاظ على الكومة)
  • عملية الفرز التصاعدي : تحريك عقدة لأعلى في الشجرة، حسب الحاجة؛ تُستخدم لاستعادة حالة الكومة بعد الإضافة. تُسمى "فرزًا" لأن العقدة تتحرك لأعلى الشجرة حتى تصل إلى المستوى الصحيح، كما في الغربال .
  • sift-down : نقل عقدة لأسفل في الشجرة، على غرار sift-up؛ يستخدم لاستعادة حالة الكومة بعد الحذف أو الاستبدال.

التنفيذ باستخدام المصفوفات

عادةً ما يتم تنفيذ الأكوام باستخدام مصفوفة ، كما يلي:

  • يمثل كل عنصر في المصفوفة عقدة من عقد الكومة، و
  • يتم تحديد علاقة الأصل/الفرع ضمنيًا من خلال مؤشرات العناصر في المصفوفة.
مثال على كومة ثنائية كاملة ذات مفاتيح عقدية عبارة عن أعداد صحيحة من 1 إلى 100 وكيفية تخزينها في مصفوفة.

في الكومة الثنائية ، يحتوي الفهرس الأول في المصفوفة على عنصر الجذر. ويحتوي الفهرسان التاليان على أبناء الجذر. وتحتوي الفهارس الأربعة التالية على أبناء العقدتين الفرعيتين للجذر، وهكذا. لذلك، عند وجود عقدة في الفهرس i ، فإن أبناءها يكونون في الفهارس ⁠2أنا+1{\displaystyle 2i+1}و​​2أنا+2{\displaystyle 2i+2}، ووالده موجود في الفهرس ⌊( i −1)/2⌋ في مصفوفة تبدأ من الفهرس ⁠0{\displaystyle 0}أو في​2أنا{\displaystyle 2i}،​​2أنا+1{\displaystyle 2i+1}، و ⌊ i /2⌋ ، على التوالي، في مصفوفة تبدأ من1{\displaystyle 1}⁠ . يجعل نظام الفهرسة البسيط هذا التنقل "صعودًا" أو "نزولًا" في الشجرة أمرًا فعالًا.

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

بعد إدراج عنصر في كومة أو حذفه منها، قد يتم انتهاك خاصية الكومة، ويجب إعادة توازن الكومة عن طريق تبديل العناصر داخل المصفوفة.

على الرغم من أن أنواع الأكوام المختلفة تنفذ العمليات بشكل مختلف، إلا أن الطريقة الأكثر شيوعًا هي كما يلي:

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

يمكن إنشاء كومة ثنائية (أو كومة من الرتبة d ) من مصفوفة عناصر معينة في زمن خطي باستخدام خوارزمية فلويد الكلاسيكية ، حيث يساوي عدد المقارنات في أسوأ الحالات 2N - 2s² ( N ) - e² ( N ) (للكومة الثنائية)، حيث s² ( N ) هو مجموع جميع أرقام التمثيل الثنائي لـ N، وe²(N ) هو أس 2 في التحليل إلى العوامل الأولية لـ N. [ 7 ] وهذا أسرع من سلسلة من عمليات الإدخال المتتالية في كومة فارغة في الأصل ، والتي تستغرق زمنًا لوغاريتميًا خطيًا. [ أ ]

المتغيرات

مقارنة الحدود النظرية للمتغيرات

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

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

التطبيقات

تتمتع بنية بيانات الكومة بالعديد من التطبيقات.

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

تطبيقات لغات البرمجة

  • توفر مكتبة C++ القياسية خوارزميات make_heap و push_heap و pop_heap لإنشاء الأكوام (التي تُنفذ عادةً كأكوام ثنائية)، والتي تعمل على مُكرِّرات الوصول العشوائي . وتتعامل هذه الخوارزميات مع المُكرِّرات كمرجع لمصفوفة، وتستخدم تحويل المصفوفة إلى كومة. كما توفر المكتبة الفئة std::priority_queue ، التي تُغلِّف هذه الإمكانيات في فئة حاوية. مع ذلك، لا يوجد دعم قياسي لعمليات الاستبدال، أو الفرز التصاعدي/التنازلي، أو التناقص/الزيادة في المفتاح.
  • تتضمن مكتبات Boost C++ مكتبة للأكوام [ 25 ] . وعلى عكس مكتبة STL، فإنها تدعم عمليات التناقص والزيادة، وتدعم أنواعًا إضافية من الأكوام: على وجه التحديد، تدعم الأكوام ذات التوزيع d ، والأكوام الثنائية، وأكوام فيبوناتشي، والأكوام المزدوجة، والأكوام المائلة.
  • يوجد تطبيق عام للكومة للغتين C و C++ يدعم كومة D-ary وكومة B-ary . وهو يوفر واجهة برمجة تطبيقات شبيهة بـ STL.
  • تتضمن المكتبة القياسية للغة البرمجة D وحدة std.container.BinaryHeap ، المُنفذة باستخدام نطاقات D. يمكن إنشاء مثيلات من أي نطاق وصول عشوائي . توفر BinaryHeap واجهة نطاق إدخال تسمح بالتكرار باستخدام عبارات foreach المدمجة في D والتكامل مع واجهة برمجة التطبيقات القائمة على النطاقات لحزمة std.algorithm .
  • يوجد في لغة هاسكل وحدة Data.Heap .
  • توفر منصة جافا (منذ الإصدار 1.5) تطبيقًا للكومة الثنائية باستخدام الفئة java.util.PriorityQueueالموجودة في إطار عمل مجموعات جافا . تُنفذ هذه الفئة افتراضيًا كومة دنيا؛ ولتنفيذ كومة عليا، يجب على المبرمج كتابة دالة مقارنة مخصصة. لا يوجد دعم لعمليات الاستبدال، أو الفرز لأعلى/لأسفل، أو إنقاص/زيادة المفتاح.
  • تحتوي لغة بايثون على وحدة heapq التي تُنفذ قائمة انتظار ذات أولوية باستخدام كومة ثنائية. وتُوفر المكتبة دالة heapreplace لدعم دمج k-way.
  • يحتوي PHP على كل من max-heap ( SplMaxHeap ) و min-heap ( SplMinHeap ) اعتبارًا من الإصدار 5.3 في مكتبة PHP القياسية.
  • يحتوي Perl على تطبيقات للأكوام الثنائية، والأكوام ذات الحدين، والأكوام الفيبوناتشية في توزيعة Heap المتوفرة على CPAN .
  • تحتوي لغة Go على حزمة heap تتضمن خوارزميات للتعامل مع الكومة، تعمل على أي نوع بيانات يفي بواجهة معينة. ولا تدعم هذه الحزمة عمليات الاستبدال، أو الإزاحة لأعلى/لأسفل، أو إنقاص/زيادة المفتاح.
  • تحتوي مكتبة Core Foundation من Apple على بنية CFBinaryHeap .
  • تتضمن مكتبة Pharo تطبيقًا لنموذج الكومة في حزمة Collections-Sequenceable، بالإضافة إلى مجموعة من حالات الاختبار. ويُستخدم نموذج الكومة في تنفيذ حلقة أحداث المؤقت.
  • تحتوي لغة البرمجة Rust على تطبيق ثنائي للكومة القصوى، BinaryHeap ، في وحدة المجموعات الخاصة بمكتبتها القياسية.
  • يحتوي .NET على فئة PriorityQueue التي تستخدم تطبيق الكومة الدنيا الرباعية (d-ary). وهي متاحة بدءًا من .NET 6.

انظر أيضاً

مراجع

  1. ↑ بلاك (محرر)، بول إي. (14 ديسمبر 2004). مدخل كلمة " heap" في قاموس الخوارزميات وهياكل البيانات . نسخة إلكترونية. المعهد الوطني الأمريكي للمعايير والتكنولوجيا ، 14 ديسمبر 2004. تم الاطلاع عليه بتاريخ 8 أكتوبر 2017 من: https://xlinux.nist.gov/dads/HTML/heap.html
  2. ↑ كورمن، توماس هـ. (2009). مقدمة في الخوارزميات . الولايات المتحدة الأمريكية: مطبعة معهد ماساتشوستس للتكنولوجيا، كامبريدج، ماساتشوستس، لندن، إنجلترا. الصفحات 151-152 . ISBN  978-0-262-03384-8.
  3. ↑ ويليامز، جيه دبليو جيه (1964)، "الخوارزمية 232 - فرز الكومة"، اتصالات رابطة آلات الحوسبة ، 7 (6): 347-348 ، doi : 10.1145/512274.3734138
  4. ↑ مكتبة بايثون القياسية، 8.4. heapq — خوارزمية قائمة الانتظار في الكومة، heapq.heappush
  5. ↑ مكتبة بايثون القياسية، 8.4. heapq — خوارزمية قائمة انتظار الكومة، heapq.heappop
  6. ↑ مكتبة بايثون القياسية، 8.4. heapq — خوارزمية قائمة الانتظار، heapq.heapreplace
  7. ↑ سوشينيك، ماريك أ. (2012)، "تحليل أولي ودقيق لأسوأ الحالات لبرنامج فلويد لبناء الكومة"، Fundamenta Informaticae ، 120 (1)، IOS Press: 75–92 ، doi : 10.3233/FI-2012-751.
  8. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  9. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  10. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  11. ↑ هايوارد، رايان؛ ماكديارميد، كولين (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 . 
  12. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  13. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  14. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  15. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  16. ↑ إياكونو، جون (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
  17. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  18. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  19. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  20. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  21. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  22. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  23. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.
  24. ↑ فريدريكسون، جريج ن. (1993)، "خوارزمية مثلى للاختيار في كومة دنيا"، المعلومات والحوسبة (ملف PDF) ، المجلد 104، دار النشر الأكاديمية، الصفحات 197-214 ، doi : 10.1006/inco.1993.1030 ، مؤرشف من النسخة الأصلية (ملف PDF) بتاريخ 2012-12-03 ، تم استرجاعه بتاريخ 2010-10-31  
  25. ↑ "Boost.Heap" . www.boost.org . تم الاطلاع عليه بتاريخ 18-07-2026 .{{cite web}}: CS1 maint: url-status ( link )
  • كومة في عالم وولفرام للرياضيات
  • شرح لكيفية عمل خوارزميات الكومة الأساسية
  • بنتلي، جون لويس (2000). لآلئ البرمجة (  الطبعة الثانية). أديسون ويسلي. الصفحات 147-162 . ISBN  0201657880.