🎐 📜 🚵🏼 فرز حسب هرم n 🔶 👩🏻 🎡

الفرز في كومة (وهو أيضًا فرز هرمي) على حبري تم تذكره بالفعل بكلمة جيدة أكثر من مرة أو مرتين ، ولكن هذه كانت دائمًا معلومات معروفة تمامًا. الجميع يعرف الكومة الثنائية المعتادة ، لكن نظرية الخوارزميات لديها أيضًا:

كومة n. مجموعة من الأكوام على أساس أرقام ليوناردو ؛ Deramide (مزيج من كومة الذاكرة المؤقتة وشجرة البحث الثنائية) ؛ كومة البطولة الصغيرة ؛ مرآة (عكسية) كومة ضعيفة كومة يونغ. كومة ذات الحدين والله يعلم ما هي أكوام أخرى ...

واقترح أذكى ممثلي علوم الكمبيوتر في سنوات مختلفة خوارزميات الفرز الخاصة بهم باستخدام هذه الهياكل الهرمية. من يهتم بما فعلوه - لأولئك الذين بدأنا سلسلة صغيرة من المقالات المخصصة للفرز باستخدام هذه الهياكل. عالم أكوام متنوعة - أتمنى أن تكون مهتما.

تمت كتابة هذه المقالة بدعم من إديسون.

نحن منخرطون في تطوير التطبيقات المحمولة وتقديم خدمات اختبار البرمجيات .

نحن نحب نظرية الخوارزميات! ؛-)

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

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

حفنة

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

أسماء أخرى من كومة الذاكرة المؤقتة - الهرم ، شجرة الفرز .

لنلقِ نظرة على كيفية تقديم مصفوفة على شكل شجرة بسهولة وكادراً مجانية.

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

على الرغم من أن الأشجار في المخططات غالبًا ما يتم تصويرها في مثل هذا المسح:

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

يتم تحديد مؤشرات سلالة العنصر i- th بواسطة العنصر الأساسي (إذا كان فهرس العنصر الأول للصفيف يعتبر مساوياً للصفر ، كما هو معتاد في غالبية لغات البرمجة):

السليل الأيسر 2 × i + 1 ،
الطفل الأيمن: 2 × i + 2

(أنا في المخططات وفي الرسوم المتحركة ، تقليديًا ، تبدأ فهارس المصفوفات بـ 1 ، حيث تختلف الصيغ قليلاً: الطفل الأيسر: 2 × i والطفل الأيمن: 2 × i + 1، ولكن هذه بالفعل فروق حسابية صغيرة).

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

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

من أجل أن تصبح شجرتنا ، التي تم إنشاؤها على أساس المصفوفة ، كومة ، يجب غربلة بشكل صحيح.

غربلة

روح فرز مجموعة غربلة.

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

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

هناك حاجة إلى غربلة من أجل جعل شجرة الفرز من شجرة عادية ولزيادة دعم الشجرة في هذه الحالة (الفرز).

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

فرز كومة :: Heapsort

الخوارزمية بسيطة في الواقع:

المرحلة 1. نقوم بتشكيل شجرة فرز من المصفوفة بأكملها. للقيام بذلك ، نمر من اليمين إلى اليسار العناصر (من الأخير إلى الأول) وإذا كان العنصر يحتوي على أحفاد ، فإننا ننخل له.
2. . , . ( ) . , .. . , — . , .

رمز Python لتنفيذ فرز هرمي كلاسيكي:

#    
def HeapSort(data):

    #    
    #   -   
    # (   )       
    for start in range((len(data) - 2) / 2, -1, -1):
        HeapSift(data, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        HeapSift(data, 0, end - 1)
    return data

#   ,      
def HeapSift(data, start, end):

    #   - ,     
    root = start 
    
    #      ,
    #   ,    
    while True:

        child = root * 2 + 1 #  
        #      -  
        if child > end: break 

        #       ,
        #      
        if child + 1 <= end and data[child] < data[child + 1]:
            child += 1

        #     ,   
        #       , 
        #       
        if data[root] < data[child]:
            data[root], data[child] = data[child], data[root]
            root = child
        else:
            break

تعقيد الخوارزمية

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

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

إجمالي التعقيد الزمني: O ( n log n ) + O ( n log n ) = O ( n log n ).
علاوة على ذلك ، فإن التصنيف الهرمي ليس له حالات متدهورة ولا أفضل. ستتم معالجة أي مصفوفة بسرعة لائقة ، ولكن لن يكون هناك تدهور أو سجلات.

الفرز كومة في المتوسط أبطأ قليلاً من الفرز السريع. ولكن بالنسبة إلى التصنيف السريع ، يمكنك التقاط مصفوفة قاتلة يعلق عليها الكمبيوتر ، ولكن بالنسبة إلى الكومة السريعة - لا.

تعقيد الوقت
أسوأ	معدل	الأفضل
O(n log n)
O(n²)	O(n log n)	O(n)

:: Ternary heapsort

دعونا نلقي نظرة على كومة ثلاثية. لن تصدقها من ثنائي ، فهي تختلف فقط في أن العقد الأصلية لا تحتوي على حد أقصى لا اثنين ، ولكن ثلاثة أحفاد. في الكومة الثلاثية لرموز العنصر i- th ، يتم حساب ثلاثة ذرية بطريقة مماثلة (إذا كان مؤشر العنصر الأول = 0):

السليل الأيسر 3 × i + 1
السليل الأوسط 3 × i + 2
السليل الأيمن 3 × i + 3

(إذا تبدأ الفهارس بالرقم 1 ، كما هو الحال في الرسوم المتحركة في هذه المقالة ، ثم في هذه الصيغ تحتاج فقط إلى طرح واحد).

عملية الفرز:

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

فرز حسب كومة n-heap :: N-narny heapsort

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

ل ط عنصر عشر للمؤشرات مجموعة (إذا كان عدد من صفر)، في N أحفاد حسابها ببساطة شديدة:

سليل 1ST: N × ط + 1
سليل 2ND: N × ط + 2
3RD سليل: N × ط + 3
...
السليل التاسع: رمز N × i + N

Python للفرز بواسطة كومة N:

#      N 
def NHeapSort(data):

    n = 3 #    

    #    
    #   -   
    # (   )       
    for start in range(len(data), -1, -1):
        NHeapSift(data, n, start, len(data) - 1) 

    #        
    #        .
    for end in range(len(data) - 1, 0, -1): 
        #       
        #    
        data[end], data[0] = data[0], data[end]
        #        
        #   
        #     
        NHeapSift(data, n, 0, end - 1)
    return data
    
#  -     N 
def NHeapSift(data, n, start, end):
    
    #   - ,     
    root = start 

    while True:
        
        #   (    )
        #   
        child = root * n + 1
        if child > end: 
            break 

        max = child
        
        #    
        for k in range(2, n + 1):
            current = root * n + k
            if current > end:
                break
                
            if data[current] > data[max]:
                max = current
        
        #     
        #        
        #  
        if data[root] < data[max]:
            data[root], data[max] = data[max], data[root]
            root = max
        else:
            break

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

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

مقطورة السلسلة التالية

لذا ، فإن العيب الرئيسي للثنائي / ternary / n-heap هو عدم القدرة على القفز في تعقيده أعلى من O ( n log n ) . الطريق للخروج من الطريق المسدود هو استخدام أصناف كومة أكثر تعقيدا في الفرز. في غضون أسبوع سوف نتعرف على ما يعتقده Edsger Dijkstra حول هذا الأمر.

انقر على الرسم المتحرك للانتقال إلى المقالة مع الفرز التالي عن طريق مجموعة

المراجع

كومة / هرم

مقالات سلسلة:

تطبيق Excel AlgoLab.xlsm
أنواع التبادل
أنواع الإدراج
فرز حسب التحديد
- أنواع الكومة: N-Pyramids
- أنواع الكومة: أرقام ليوناردو
- نوع الكومة: كومة ضعيفة
- أنواع الحفريات: شجرة ديكارتية
- فرز كومة أخرى: كومة مرآة ، كومة صغيرة ، غربلة من أسفل إلى أعلى
- أنواع الكومة: Jung Heap
دمج الأنواع
فرز حسب التوزيع
الفرز الهجين

أضاف تطبيق AlgoLab الفرز بواسطة n-heap. لتحديد عدد الأحفاد ، في التعليق على خلية هذا النوع ، تحتاج إلى تحديد رقم لـ n. يتراوح نطاق القيم الممكنة من 2 إلى 5 (لا معنى له أكثر من ذلك ، لأنه بالنسبة إلى n> = 6 ، لا يمكن ضمان احتواء الرسوم المتحركة بثلاثة مستويات من التعشيش بمقياس عادي على الشاشة).

فرز حسب هرم n