كومة ضعيفة

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

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

تستخدم خوارزمية الفرز باستخدام الأكوام الضعيفة، weak-heapsort، عددًا من المقارنات يقترب من الحد الأدنى النظري لعدد المقارنات المطلوبة لفرز قائمة ، لذا فهي مفيدة بشكل خاص عندما تكون المقارنة مكلفة، كما هو الحال عند مقارنة السلاسل باستخدام خوارزمية ترتيب Unicode الكاملة .

وصف

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

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

ويمكن التعبير عن ذلك كشجرة ثنائية، مما يؤدي إلى الثوابت التالية: [ 1 ]

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

الشرط الأخير هو نتيجة لحقيقة أن الشجرة الثنائية الضمنية هي شجرة ثنائية كاملة .

يتطابق هيكل هذه الشجرة بشكل دقيق مع ترتيب الشجرة الثنائية الضمنية التقليدية القائمة على 1 ( Ahnentafel )، حيث يكون للعقدة k شقيق تالٍ (ابن أيسر) مرقم 2k وابن أول (ابن أيمن) مرقم 2k + 1 ، وذلك بإضافة جذر إضافي مرقم 0. لا يملك هذا الجذر أي أشقاء، بل ابن أول فقط، وهو العقدة 1 ( 2 × 0 + 1 ).

يشبه هذا الهيكل إلى حد كبير هيكل الكومة الثنائية، حيث تتكون الشجرة ذات الارتفاع h من جذر بالإضافة إلى أشجار ذات ارتفاعات h − 1 ، h − 2 ، ...، 1. الكومة الضعيفة المثالية (بدون أوراق مفقودة) التي تحتوي على 2n عنصرًا متماثلة تمامًا مع الكومة الثنائية من نفس الحجم، [ 2 ] ولكن الخوارزميتين تتعاملان مع الأحجام التي ليست قوة للعدد 2 بشكل مختلف: تستخدم الكومة الثنائية أشجارًا مثالية متعددة، بينما تستخدم الكومة الضعيفة شجرة واحدة غير مثالية.

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

في الشجرة الثنائية الضمنية، العقدة k ذات البت العكسي r k لها أب ⌊ ⁠ k / 2 ⁠ ⌋ ، وابن أيسر 2 k + r k ، وابن أيمن 2 k + 1 − r k .

عند النظر إلى الكومة الضعيفة كشجرة متعددة الفروع، ترتبط كل عقدة بعقدتين أخريين: "الشقيق التالي" و"الابن الأول". في الشجرة الضمنية، تكون الروابط ثابتة، لذا يُشار إلى أي من الرابطين هو الشقيق وأيهما هو الابن الأول بواسطة البت العكسي.

عمليات على أكوام ضعيفة

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

تحتوي العقدة ذات الارتفاع h على h − 1 أبناء: الابن الأول ذو الارتفاع h − 1 ، والابن الثاني ذو الارتفاع h − 2 ، وهكذا حتى الابن الأخير ذو الارتفاع 1. ويمكن العثور على هؤلاء الأبناء باتباع رابط الابن الأول ثم روابط الأشقاء التالية.

كما أن لها أشقاءً لاحقين بارتفاع h − 1 و h − 2 وما إلى ذلك.

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

على الرغم من أن السلف المميز قد يكون على ارتفاع log 2 n مستوى في الشجرة، فإن متوسط ​​المسافة هو 2. (وهو على الأقل 1 ، وفي نصف الوقت نستدعي الدالة بشكل متكرر، لذا فإن D = 1 + D /2 ، مما يعني أن D = 2 ). وبالتالي، فإن حتى خوارزمية تكرارية بسيطة لإيجاد السلف المميز كافية.

كما هو الحال في أكوام ذات الحدين، فإن العملية الأساسية في الأكوام الضعيفة هي دمج كومين متساويين في الارتفاع h ، لتكوين كومة ضعيفة ارتفاعها h + 1. يتطلب هذا مقارنة واحدة فقط بين الجذرين. الجذر الأكبر (بافتراض كومة عظمى) هو الجذر النهائي. أول ابن له هو الجذر الخاسر، الذي يحتفظ بأبنائه (الشجرة الفرعية اليمنى). أما أبناء الجذر الفائز فيُعتبرون أشقاءً للجذر الخاسر.

يمكن إجراء هذه العملية على بنية الشجرة الضمنية لأن الكومات التي يتم دمجها ليست عشوائية أبدًا. بل يتم تشكيل الكومتين كجزء من عملية فرز عقدة ما في الشجرة متعددة الاتجاهات.

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

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

بعد مقارنة الجذرين، تتم عملية الدمج بإحدى الطريقتين التاليتين:

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

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

ومع ذلك، فإن السلف السابق ليس والدًا آمنًا لأبناء الجذر الأول القدامى، لأنه أقل من الجذر الأول وبالتالي ليس من المؤكد أنه أكبر من أو يساوي جميع أبنائه.

عن طريق تبديل الأبناء الثنائيين، يتم تخفيض رتبة المجموعة الفرعية المناسبة من أبناء السلف المُخفَّض (والذين تقل رتبتهم عنه أو تساويها) معه. أما أشقاء السلف المُخفَّض الجدد فهم أبناء الجذر الأول القدامى، الذين تمت ترقيتهم، والذين تقل رتبتهم عن الجذر الأول المُرقّى أو تساويه.

بعد هذه العملية، من غير المؤكد ما إذا كان الثابت سيظل قائماً بين السلف المميز الجديد وسلفه المميز ، لذلك يتم تكرار العملية حتى يتم الوصول إلى الجذر.

فرز الكومة الضعيفة

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

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

كما هو الحال مع خوارزمية فرز الكومة، إذا كانت المصفوفة المراد فرزها أكبر من ذاكرة التخزين المؤقت لوحدة المعالجة المركزية ، فإن الأداء يتحسن إذا تم دمج الأشجار الفرعية بمجرد توفر شجرتين فرعيتين بنفس الحجم، بدلاً من دمج جميع الأشجار الفرعية على مستوى واحد قبل الانتقال إلى المستوى التالي. [ 4 ]

يمكن إجراء الفرز التنازلي في كومة ضعيفة باستخدام h = ⌈ log 2 n ⌉ مقارنة، على عكس 2 log 2 n للكومة الثنائية، أو 1.5 log 2 n لنوع " فرز الكومة من الأسفل إلى الأعلى ". يتم ذلك عن طريق "الدمج التصاعدي": بعد تبديل الجذر مع آخر عنصر في الكومة، يتم العثور على آخر ابن (ارتفاعه 1) للجذر. يتم دمج هذا الابن مع الجذر (سلفه المميز)، مما ينتج عنه كومة صالحة بارتفاع 2 عند الجذر العام. ثم يتم الانتقال إلى الشقيق السابق (الأب الثنائي) لآخر عقدة مدمجة، ويتم الدمج مرة أخرى. تُكرر هذه العملية حتى الوصول إلى الجذر، وعندها ستكون الكومة صحيحة للشجرة بأكملها.

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

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

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

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

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

التاريخ والتطبيقات

قدّم داتون (1993) مفهوم الأكوام الضعيفة كجزء من خوارزمية فرز الأكوام المعدّلة ، والتي (على عكس فرز الأكوام القياسي باستخدام الأكوام الثنائية) يمكن استخدامها لفرز n عنصرًا باستخدام n  log 2 n  + O ( n )  مقارنة فقط. [ 3 ] [ 5 ] وقد تمّت دراستها لاحقًا كبنية بيانات لقوائم الانتظار ذات الأولوية، وهي أكثر قابلية للتطبيق بشكل عام. [ 6 ] [ 7 ]

مراجع

  1. ↑ إيدلكامب، ستيفان (26 مايو 2011)، بيترس، فريدا؛ بلاك، بول إي. (محررون)، "الكومة الضعيفة" ، قاموس الخوارزميات وهياكل البيانات ، تم استرجاعه في 1 ديسمبر 2015
  2. 1 2 إيدلكامب، ستيفان؛ المصري، عمرو؛ كاتاجاينن، يركي (أكتوبر 2012)، "بنية بيانات الكومة الضعيفة: المتغيرات والتطبيقات" (ملف PDF) ، مجلة الخوارزميات المنفصلة ، ​​16 : 187-205 ، CiteSeerX 10.1.1.455.1213 ، doi : 10.1016/j.jda.2012.04.010 ، MR 2960353  .
  3. 1 2 3 داتون، رونالد د. (1993)، "فرز الكومة الضعيفة"، BIT ، 33 (3): 372-381 ، doi : 10.1007/bf01990520 ، S2CID 5387832 .
  4. ↑ بوجيسن، جيسبر؛ كاتاجاينن، يركي؛ سبورك، ماز (2000). "دراسة حالة هندسة الأداء: بناء الكومة" (PostScript) . مجلة ACM للخوارزميات التجريبية . 5 (15). CiteSeerX 10.1.1.35.3248 . doi : 10.1145/351827.384257 . S2CID 16705375 .  مصدر بديل لملف PDF .
  5. ↑ إيدلكامب، ستيفان؛ ويجنر، إنجو (2000)، "حول أداء خوارزمية فرز الكومة الضعيفة "، مؤتمر ستاكس 2000 (ملف PDF) ، سلسلة محاضرات في علوم الحاسوب، المجلد 1770، دار نشر سبرينغر، الصفحات 254-266 ، CiteSeerX 10.1.1.21.1863 ، doi : 10.1007/3-540-46541-3_21 ، ISBN    978-3-540-67141-1.
  6. ↑ برون، أسجر؛ إيدلكامب، ستيفان؛ كاتاجاينن، يركي؛ راسموسن، ينس (2010). "التقييم المعياري القائم على السياسات للأكوام الضعيفة وما يرتبط بها" (ملف PDF) . وقائع الندوة الدولية التاسعة حول الخوارزميات التجريبية (SEA 2010) . سلسلة محاضرات في علوم الحاسوب. المجلد 6049. سبرينغر-فيرلاغ. الصفحات 424-435 . doi : 10.1007/978-3-642-13193-6_36 . ISBN   978-3-642-13192-9تمت أرشفة النسخة الأصلية (PDF) بتاريخ 2017-08-11..
    • برون، أسجر؛ إيدلكامب، ستيفان؛ كاتاجاينن، يركي؛ راسموسن، ينس (2010). "التقييم المعياري القائم على السياسات للأكوام الضعيفة وما يرتبط بها". الخوارزميات التجريبية (ملف PDF) . سلسلة محاضرات في علوم الحاسوب. المجلد  6049. الصفحات 424-435 . doi : 10.1007/978-3-642-13193-6_36 . ISBN  978-3-642-13192-9. S2CID 1334592 . مؤرشف من الأصل (PDF) بتاريخ 2016-12-27 – عبر Semantic Scholar. 
  7. ↑ إيدلكامب، ستيفان؛ المصري، عمرو؛ كاتاجاينن، يركي (2012)، "عائلة طوابير الأولوية ذات الكومة الضعيفة: النظرية والتطبيق" (ملف PDF) ، وقائع الندوة الثامنة عشرة للحوسبة: ندوة أستراليا ونيوزيلندا النظرية (CATS 2012) ، المجلد 128، دارلينجهيرست، أستراليا: الجمعية الأسترالية للحاسبات، الصفحات 103-112 ، ISBN   978-1-921770-09-8.

للمزيد من القراءة

  • إيدلكامب، ستيفان؛ المصري، عمرو؛ كاتاجاينن، يركي (نوفمبر 2013). "هندسة الأكوام الضعيفة" (ملف PDF) . مجلة الخوارزميات المنفصلة . 23 : 83-97 . doi : 10.1016/j.jda.2013.07.002 . نقدم في هذا البحث قائمة بالخوارزميات التي تُحسّن الخوارزميات القياسية بطرق متنوعة. ونعتمد في معايير التحسين على أسوأ وقت تشغيل، وعدد التعليمات، وتوقعات التفرعات الخاطئة، وأخطاء ذاكرة التخزين المؤقت، ومقارنات العناصر، ونقل العناصر.
  • إيدلكامب، ستيفان؛ المصري، عمرو؛ كاتاياينن، يركي؛ فايس، أرمين (يوليو 2013). الأكوام الضعيفة وما يرتبط بها: التطورات الحديثة . الخوارزميات التوافقية - ورشة العمل الدولية الرابعة والعشرون. روان ، فرنسا. doi : 10.1007/978-3-642-45278-9_1