كومة الاقتران

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

كومة الاقتران هي نوع من هياكل بيانات الكومة ، تتميز بسهولة تنفيذها نسبيًا وأدائها العملي الممتاز ، وقد قدمها مايكل فريدمان وروبرت سيدجويك ودانيال سليتور وروبرت تارجان عام 1986. [ 1 ] تُعد أكوام الاقتران هياكل شجرية متعددة الاتجاهات مرتبة حسب ترتيب الكومة ، ويمكن اعتبارها أكوام فيبوناتشي مبسطة . وتُعتبر خيارًا قويًا لتنفيذ خوارزميات مثل خوارزمية بريم للشجرة الممتدة الدنيا ، [ 2 ] وتدعم العمليات التالية (بافتراض وجود كومة دنيا):

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

استُلهم تحليل التعقيد الزمني لأكوام الاقتران في البداية من تحليل أشجار التفرع . [ 1 ] يبلغ متوسط ​​الوقت المستهلك لكل عملية حذف-min قيمة O ( log n ) ، وتُنفذ عمليات البحث-min والدمج والإدراج في زمن O (1) . [ 3 ]

عند إضافة عملية إنقاص المفتاح ، يصبح تحديد زمن التشغيل التقاربي الدقيق لأكوام الاقتران أمرًا صعبًا. في البداية، تم افتراض أن التعقيد الزمني لهذه العملية، استنادًا إلى أسس تجريبية، هو O (1) [ 4 ] ، لكن فريدمان أثبت أن الزمن المستهلك لكل عملية إنقاص مفتاح هو على الأقلΩ(سجل⁡سجل⁡ن){\displaystyle \Omega (\log \log n)}بالنسبة لبعض تسلسلات العمليات. [ 5 ] باستخدام حجة استهلاك مختلفة، أثبت بيتي بعد ذلك أن عمليات الإدراج والدمج وتقليل المفتاح تعمل جميعها فييا(22سجل⁡سجل⁡ن){\displaystyle O(2^{2{\sqrt {\log \log n}}})}الوقت المستهلك، وهوo(سجل⁡ن){\displaystyle o(\log n)}[ 6 ] قدم المصري لاحقًا تفاصيلًا عن أكوام الاقتران (الكسولة، والدمج) التي يتم فيها تشغيل مفاتيح التناقص فييا(سجل⁡سجل⁡ن){\displaystyle O(\log \log n)}للوقت المستهلك والعمليات الأخرى حدود استهلاك مثالية، [ 7 ] [ 8 ] ولكن ليس لها حدود دقيقة.Θ(سجل⁡سجل⁡ن){\displaystyle \Theta (\log \log n)}يُعرف الربط ببنية البيانات الأصلية. [ 3 ] [ 6 ]

على الرغم من أن الأداء التقاربي لأكوام الاقتران أسوأ من خوارزميات قوائم الانتظار ذات الأولوية الأخرى مثل أكوام فيبوناتشي ، التي تؤدي وظيفة تقليل المفتاح فييا(1){\displaystyle O(1)}مع مراعاة الوقت المستهلك، يكون الأداء العملي ممتازًا. أجرى جونز [ 9 ] ولاركين وسين وتارجان [ 10 ] تجارب على أكوام الاقتران وهياكل بيانات الأكوام الأخرى. وخلصوا إلى أن أكوام d-ary، مثل الأكوام الثنائية، أسرع من جميع تطبيقات الأكوام الأخرى عندما لا تكون عملية إنقاص المفتاح مطلوبة (وبالتالي لا حاجة لتتبع موقع العقد في الكومة خارجيًا)، ولكن عندما تكون عملية إنقاص المفتاح مطلوبة، غالبًا ما تكون أكوام الاقتران أسرع من أكوام d-ary، ودائمًا تقريبًا أسرع من أكوام المؤشرات الأخرى، بما في ذلك هياكل البيانات مثل أكوام فيبوناتشي التي تُعد نظريًا أكثر كفاءة. درس تشين وآخرون [ 11 ] قوائم الانتظار ذات الأولوية خصيصًا لاستخدامها مع خوارزمية ديكسترا، وخلصوا إلى أنه في الحالات العادية، يؤدي استخدام كومة d-ary بدون إنقاص المفتاح (بدلاً من ذلك، تكرار العقد في الكومة وتجاهل النسخ الزائدة) إلى أداء أفضل، على الرغم من ضمانات الأداء النظرية الأقل.

بناء

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

نوع PairingTree[Elem] = Heap(elem: Elem, subheaps: List[PairingTree[Elem]]) نوع PairingHeap[Elem] = Empty | PairingTree[Elem]

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

العمليات

اندماج

يؤدي دمج الكومة الفارغة مع الكومة الأخرى إلى إرجاع الكومة الأخرى، وإلا يتم إرجاع كومة جديدة تحتوي على أصغر عنصرين جذريين كعنصر جذري لها، ويتم إضافة الكومة ذات الجذر الأكبر إلى قائمة الكومات الفرعية:

دالة meld(heap1, heap2: PairingHeap[Elem]) -> PairingHeap[Elem] إذا كانت heap1 فارغة، تُرجع heap2. وإذا كانت heap2 فارغة ، تُرجع heap1. وإذا كان heap1.elem < heap2.elem ، تُرجع Heap(heap1.elem, heap2 :: heap1.subheaps). وإلا ، تُرجع Heap(heap2.elem, heap1 :: heap2.subheaps) .

أدخل

أسهل طريقة لإدراج عنصر في كومة هي دمج الكومة مع كومة جديدة تحتوي فقط على هذا العنصر وقائمة فارغة من الكومات الفرعية:

دالة insert(elem: Elem, heap: PairingHeap[Elem]) -> PairingHeap[Elem] تُرجع meld(Heap(elem, []), heap)

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

تقوم الدالة find-min ببساطة بإرجاع العنصر الجذر للكومة:

دالة find-min(heap: PairingHeap[Elem]) -> Elem إذا كانت الكومة فارغة، خطأ وإلا تُرجع heap.elem

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

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

دالة حذف أصغر عنصر في الكومة (heap: PairingHeap[Elem]) -> PairingHeap[Elem] إذا كانت الكومة فارغة، خطأ، وإلا تُرجع دالة دمج الأزواج (heap.subheaps).

يستخدم هذا الدالة المساعدة merge-pairs :

دالة دمج الأزواج (قائمة: قائمة[شجرة الاقتران[عنصر]]) -> كومة الاقتران[عنصر]) إذا كان طول(القائمة) يساوي صفرًا ، تُرجع فارغة، وإذا كان طول(القائمة) يساوي واحدًا ، تُرجع القائمة[0]، وإلا تُرجع دمج(دمج(القائمة[0]، القائمة[1])، دمج الأزواج(القائمة[2..]))

يمكن ملاحظة أن هذا يطبق بالفعل استراتيجية الدمج الموصوفة ذات المرحلتين من اليسار إلى اليمين ثم من اليمين إلى اليسار من خلال هذا الاختزال:

 merge-pairs([H1, H2, H3, H4, H5, H6, H7]) => دمج(دمج(H1، H2)، دمج الأزواج([H3، H4، H5، H6، H7])) # ادمج H1 و H2 لتكوين H12، ثم بقية القائمة => دمج( H12 ، دمج(دمج(H3، H4)، دمج الأزواج([H5، H6، H7]))) # ادمج H3 و H4 لتكوين H34، ثم باقي القائمة => meld(H12, meld( H34 , meld(meld(H5, H6), دمج الأزواج([H7])))) # ادمج H5 و H6 في H56، ثم بقية القائمة => دمج (H12، دمج (H34، دمج ( H56 ، H7))) # غيّر الاتجاه، وادمج الكومتين الناتجتين الأخيرتين، لتحصل على H567 => دمج(H12، دمج(H34، H567 )) # ادمج الكومتين الناتجتين الأخيرتين، لتحصل على H34567 => دمج(H12، H34567 ) # وأخيرًا، ادمج الزوج الأول مع نتيجة دمج الباقي => H1234567

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

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

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

مراجع

  1. فريدمان ، مايكل ل .؛ سيدجويك ، روبرت ؛ سليتور، دانيال د .؛ تارجان، روبرت إي. (1986). "كومة الاقتران: شكل جديد من الكومة ذاتية التعديل" (ملف PDF) . Algorithmica . 1 ( 1-4 ): 111-129 . doi : 10.1007 /BF01840439 . S2CID 23664143 . 
  2. ↑ ميلهورن، كورت ؛ ساندرز، بيتر (2008). الخوارزميات وهياكل البيانات: مجموعة الأدوات الأساسية (ملف PDF) . سبرينغر. ص 231. 
  3. 1 2 3 إياكونو، جون (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
  4. ↑ ستاسكو، جون ت .؛ فيتر، جيفري س. (1987)، "أكوام الاقتران: تجارب وتحليل" (ملف PDF) ، اتصالات ACM ، 30 (3): 234-249 ، CiteSeerX 10.1.1.106.2988 ، doi : 10.1145/214748.214759 ، S2CID 17811811  
  5. ↑ فريدمان، مايكل ل. (1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة ACM . 46 (4): 473-501 . doi : 10.1145/320211.320214 . S2CID 16115266. مؤرشف من الأصل (ملف PDF) بتاريخ 21 يوليو 2011. تم الاطلاع عليه بتاريخ 3 مايو 2011 . 
  6. 1 2 بيتي، سيث (2005)، "نحو تحليل نهائي لأكوام الاقتران" (ملف PDF) ، وقائع الندوة السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب (ملف PDF) ، الصفحات 174-183 ، doi : 10.1109/SFCS.2005.75 ، ISBN  0-7695-2468-0، S2CID 2717102 
  7. ↑ المصري، عمرو (2009)، " تقليل تكلفة إقران الأكوام بـ O (log log n ) " (ملف PDF) ، وقائع الندوة السنوية العشرون لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 471-476 ، CiteSeerX 10.1.1.502.6706 ، doi : 10.1137/1.9781611973068.52  
  8. ↑ المصري، عمرو (نوفمبر 2017). "نحو أكوام مثالية ذاتية التعديل" . معاملات ACM في الخوارزميات . 13 (4): 1-14 . doi : 10.1145/3147138 . S2CID 1182235 . 
  9. ↑ جونز، دوغلاس و. (1986). "مقارنة تجريبية بين تطبيقات قائمة الانتظار ذات الأولوية وتطبيقات مجموعة الأحداث". اتصالات رابطة مكائن ​​الحوسبة . 29 (4): 300-311 . CiteSeerX 10.1.1.117.9380 . doi : 10.1145/5684.5686 . S2CID 43650389 .  
  10. ↑ لاركين، دانيال هـ.؛ سين، سيدهارتا؛ تارجان، روبرت إي. (2014)، "دراسة تجريبية أساسية لقوائم الانتظار ذات الأولوية"، وقائع ورشة العمل السادسة عشرة حول هندسة الخوارزميات والتجارب ، ص 61-72 ، arXiv : 1403.0252 ، doi : 10.1137/1.9781611973198.7 ، ISBN  978-1-61197-319-8، S2CID 15216766 
  11. ^ تشين، مو؛ شودري، رضاول علم؛ راماشاندران، فيجايا؛ روش، ديفيد لان؛ تونغ ، لينجلينج (12 أكتوبر 2007). قوائم الانتظار ذات الأولوية وخوارزمية ديكسترا (PDF) (التقرير الفني). جامعة تكساس. TR-07-54.
  12. 1 2 3 4 كورمين، توماس هـ . ليسرسون، تشارلز إي . ريفست، رونالد ل. (1990). مقدمة في الخوارزميات ( الطبعة الأولى). مطبعة معهد ماساتشوستس للتكنولوجيا وماكجرو هيل. رقم ISBN  0-262-03141-8.
  13. 1 2 3 سليتور، دانيال دومينيك ؛ تارجان، روبرت إندري (فبراير 1986). "الأكوام ذاتية التعديل" . مجلة SIAM للحوسبة . 15 (1): 52-69 . CiteSeerX 10.1.1.93.6678 . doi : 10.1137/0215004 . ISSN 0097-5397 .  
  14. 1 2 تارجان، روبرت (1983). "3.3. أكوام اليسار". هياكل البيانات وخوارزميات الشبكات . ص 38-42 . doi : 10.1137/1.9781611970265 . ISBN  978-0-89871-187-5.
  15. ↑ هايوارد، رايان؛ ماكديارميد، كولين (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 . 
  16. ↑ "الكومة ذات الحدين | موسوعة الرياضيات والعلوم الرائعة" . brilliant.org . تم الاطلاع عليه بتاريخ 30-09-2019 .
  17. 1 2 برودال، جيرث ستولتينغ؛ أوكاساكي، كريس (نوفمبر 1996)، "طوابير الأولوية الوظيفية البحتة المثلى"، مجلة البرمجة الوظيفية ، 6 (6): 839-857 ، doi : 10.1017/s095679680000201x
  18. ↑ أوكاساكي، كريس (1998). "10.2. التجريد الهيكلي". هياكل البيانات الوظيفية البحتة ( الطبعة الأولى). الصفحات 158-162 . ISBN   9780521631242.
  19. ↑ تاكاوكا، تاداو (1999)، نظرية الأكوام 2-3 (ملف PDF) ، ص 12 
  20. ↑ فريدمان، مايكل لورانس (يوليو 1999). "حول كفاءة أكوام الاقتران وهياكل البيانات ذات الصلة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 46 (4): 473-501 . doi : 10.1145/320211.320214 .
  21. ↑ بيتي، سيث (2005). نحو تحليل نهائي لأكوام الاقتران (ملف PDF) . وقائع ندوة FOCS '05 السنوية السادسة والأربعين لمؤسسة IEEE حول أسس علوم الحاسوب. الصفحات 174-183 . CiteSeerX 10.1.1.549.471 . doi : 10.1109/SFCS.2005.75 . ISBN   0-7695-2468-0.
  22. ^ هيوبلر، بيرنهارد. سين، سيدهارتا؛ تارجان ، روبرت إي. (نوفمبر 2011). "أكوام الاقتران بالرتبة" (PDF) . سيام ج. الحوسبة . 40 (6): 1463–1485 . دوى : 10.1137/100785351 .
  23. ↑ فريدمان، مايكل لورانس ؛ تارجان، روبرت إي. (يوليو 1987). "أكوام فيبوناتشي واستخداماتها في خوارزميات تحسين الشبكات المحسّنة" (ملف PDF) . مجلة رابطة آلات الحوسبة . 34 (3): 596-615 . CiteSeerX 10.1.1.309.8927 . doi : 10.1145/28869.28874 . 
  24. ↑ برودال، جيرث ستولتينغ ؛ لاغوجيانيس، جورج؛ تارجان، روبرت إي. (2012). أكوام فيبوناتشي الصارمة (ملف PDF) . وقائع الندوة الرابعة والأربعين حول نظرية الحوسبة - STOC '12. الصفحات 1177-1184 . CiteSeerX 10.1.1.233.1740 . doi : 10.1145/2213977.2214082 . ISBN   978-1-4503-1245-5.
  25. ↑ برودال، جيرث س. ( 1996)، "طوابير الأولوية الفعالة في أسوأ الحالات" (ملف PDF) ، وقائع الندوة السنوية السابعة لجمعية ACM-SIAM حول الخوارزميات المنفصلة ، ​​الصفحات 52-58 
  26. ↑ غودريتش، مايكل ت .؛ تاماسيا، روبرتو (2004). "7.3.6. بناء الكومة من الأسفل إلى الأعلى". هياكل البيانات والخوارزميات في جافا ( الطبعة الثالثة). ص 338-341 . ISBN   0-471-46983-1.