يُشار إلى الكومة على أنها 'مرتبة جزئيًا' وليست 'مرتبة جزئيًا'. كلمة 'فرز' تعني الترتيب الكامل (الفرز الكامل). لا يتم طلب الكومة بشكل تعسفي. يتم ترتيب الكومة جزئيًا باتباع معيار (نمط) ، كما هو موضح أدناه.
لذلك ، يتكون heapsort من مرحلتين: بناء الكومة واستخراج العنصر المرتب من أعلى الكومة. في المرحلة الثانية ، بعد كل عملية استخراج ، يتم إعادة بناء الكومة. تعد كل عملية إعادة بناء أسرع من عملية البناء الأصلية حيث تتم إعادة البناء من بناء سابق ، حيث تمت إزالة عنصر واحد. وبهذا ، يفرز heapsort قائمة لم يتم فرزها تمامًا.
الهدف من هذه المقالة هو شرح الفرز الزمني بإيجاز ثم إنتاج تعقيده الزمني (انظر معنى تعقيد الوقت أدناه). نحو النهاية ، يتم الترميز في C ++.
الحد الأدنى من الكومة
يمكن أن تكون الكومة الحد الأدنى من الكومة أو الحد الأقصى للكومة. الحد الأقصى للكوم هو العنصر الذي يكون فيه العنصر الأول هو العنصر الأعلى ، ويتم ترتيب الشجرة بأكملها أو القائمة المقابلة جزئيًا بترتيب تنازلي. الكومة الدقيقة هي التي يكون فيها العنصر الأول هو أصغر عنصر ، ويتم ترتيب القائمة بأكملها جزئيًا بترتيب تصاعدي. في هذه المقالة ، يتم اعتبار الحد الأدنى من الكومة فقط. ملاحظة: في موضوع الكومة ، يُطلق على العنصر أيضًا اسم العقدة.
الكومة هي شجرة ثنائية كاملة. يمكن التعبير عن الشجرة الثنائية كمصفوفة (قائمة) ؛ اقرأ من أعلى إلى أسفل ومن اليسار إلى اليمين. خاصية الكومة لـ min-heap هي أن العقدة الأصلية أقل من أو تساوي كل من الفرعين الفرعيين. مثال على قائمة غير مرتبة:
| 9 | 19 | 24 | 5 | 3 | أحد عشر | 14 | 22 | 7 | 6 | 17 | خمسة عشر | لا شيء | لا شيء | لا شيء |
| 0 | 1 | اثنين | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | أحد عشر | 12 | 13 | 14 |
الصف الأول من هذا الجدول هو عناصر المصفوفة. في الصف الثاني توجد الفهارس الصفرية. يمكن التعبير عن قائمة العناصر هذه على شكل شجرة. تمت إضافة العناصر الفارغة لعمل شجرة ثنائية كاملة. بالمعنى الدقيق للكلمة ، العناصر الفارغة ليست جزءًا من القائمة (الشجرة). هذه القائمة ليس لها ترتيب ، لذلك فهي ليست كومة حتى الآن. سيصبح كومة عندما يكون لديه طلب جزئي ، وفقًا لخاصية الكومة.
العلاقة بين العقد والفهارس
تذكر أن الكومة عبارة عن شجرة ثنائية كاملة قبل تكوين الكومة (خاصية الكومة). القائمة السابقة ليست كومة حتى الآن ، لأن العناصر لا تخضع لخاصية الكومة. يصبح كومة بعد إعادة ترتيب العناصر بترتيب جزئي وفقًا لخاصية min-heap. يمكن اعتبار الترتيب الجزئي على أنه فرز جزئي (على الرغم من أن كلمة 'فرز' تعني ترتيبًا كاملاً).
سواء كانت الشجرة الثنائية عبارة عن كومة أم لا ، فإن كل والد لديه طفلان ، باستثناء العقد الورقية (الأخيرة). هناك علاقة رياضية بين الفهارس بين كل والد وأبنائه. على النحو التالي: إذا كان الوالد في الفهرس i ، فسيكون الطفل الأيسر في الفهرس:
اثنين * أنا + 1والطفل المناسب في الفهرس:
اثنين * أنا + اثنينهذا من أجل الفهرسة الصفرية. وهكذا ، يكون للوالد في الفهرس 0 طفله الأيسر عند الفهرس 2 × 0 + 1 = 1 وطفله الأيمن عند 2 × 0 + 2 = 2. الوالد في الفهرس 1 لديه طفله الأيسر عند الفهرس 2 × 1 + 1 = 3 والطفل الأيمن عند الفهرس 2 × 1 + 2 = 4 ؛ وهلم جرا.
من خلال خاصية min-heap ، يكون الوالد في i أقل من أو يساوي الطفل الأيسر عند 2i + 1 وأقل من أو يساوي الطفل الأيمن عند 2i + 2.
كومة
الكومة تعني بناء كومة. يعني إعادة ترتيب عناصر القائمة (أو الشجرة المقابلة) بحيث تفي بخاصية الكومة. في نهاية عملية الكومة ، تكون القائمة أو الشجرة عبارة عن كومة.
إذا تم تكديس القائمة السابقة التي لم يتم فرزها ، فستصبح:
| 3 | 5 | أحد عشر | 7 | 6 | خمسة عشر | 14 | 22 | 9 | 19 | 17 | 24 | لا شيء | لا شيء | لا شيء |
| 0 | 1 | اثنين | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | أحد عشر | 12 | 13 | 14 |
ملاحظة: هناك 12 عنصرًا وليس 15 عنصرًا في القائمة. في الصف الثاني توجد الفهارس. في عملية بناء الكومة ، يجب فحص العناصر ومبادلة بعضها.
لاحظ أن أصغر عنصر وأول عنصر هو 3. يتبع باقي العناصر بطريقة تصاعدية ولكن متموجة. إذا كان الأطفال الأيمن والأيسر في الموضعين 2i + 1 و 2i + 2 أكبر من أو يساوي الأب في i ، فهذا يعني أن هذا الحد الأدنى من الكومة. هذا ليس الترتيب الكامل أو الفرز. هذا ترتيب جزئي ، وفقًا لخاصية الكومة. ومن هنا تبدأ المرحلة التالية لفرز الكومة.
زيادة التعقيد الزمني
تعقيد الوقت هو وقت التشغيل النسبي لبعض التعليمات البرمجية. يمكن اعتباره عدد العمليات الرئيسية لإكمال هذا الرمز. هناك خوارزميات مختلفة لبناء الكومة. الأكثر كفاءة والأسرع هو تقسيم القائمة باستمرار إلى قسمين ، والتحقق من العناصر من الأسفل ، ثم القيام ببعض تبديل العناصر. لنفترض أن N هو عدد العناصر العملية في القائمة. باستخدام هذه الخوارزمية ، يكون الحد الأقصى لعدد العمليات الرئيسية (المبادلة) هو N.
ا ( ن )حيث n هي N وهو أقصى عدد ممكن من العمليات الرئيسية. هذا التدوين يسمى تدوين Big-O. يبدأ بحرف O بأحرف كبيرة ، متبوعًا بأقواس. يوجد داخل الأقواس تعبير لأكبر عدد ممكن من العمليات.
تذكر: يمكن أن تصبح الإضافة عملية ضرب إذا استمر نفس الشيء المضاف في التكرار.
الرسم التوضيحي Heapsort
سيتم استخدام القائمة السابقة التي لم يتم فرزها لتوضيح فرز الكومة. القائمة المقدمة هي:
9 19 24 5 3 أحد عشر 14 22 7 6 17 خمسة عشرالكومة الصغرى الناتجة من القائمة هي:
3 5 أحد عشر 7 6 خمسة عشر 14 22 9 19 17 24المرحلة الأولى في heapsort هي إنتاج الكومة التي تم إنتاجها. هذه قائمة مرتبة جزئيا. إنها ليست قائمة مرتبة (مرتبة بالكامل).
تتكون المرحلة الثانية من إزالة أصغر عنصر ، وهو العنصر الأول ، من الكومة ، وإعادة كومة الكومة المتبقية ، وإزالة أقل العناصر في النتائج. دائمًا ما يكون أقل عنصر هو العنصر الأول في الكومة المعاد تكوينها. لا يتم إزالة العناصر والتخلص منها. يمكن إرسالها إلى مصفوفة مختلفة بالترتيب الذي تمت إزالتها به.
في النهاية ، ستحتوي المصفوفة الجديدة على جميع العناصر مرتبة (بالكامل) بترتيب تصاعدي ؛ ولم يعد أمرًا جزئيًا فقط.
في المرحلة الثانية ، أول شيء يجب فعله هو إزالة 3 ووضعه في المصفوفة الجديدة. النتائج هي:
3و
5 أحد عشر 7 6 خمسة عشر 14 22 9 19 17 24يجب تكديس العناصر المتبقية قبل استخراج العنصر الأول. يمكن أن تصبح كومة العناصر المتبقية:
5 6 7 9 خمسة عشر 14 22 أحد عشر 19 17 24استخراج 5 وإضافة إلى القائمة الجديدة (مصفوفة) يعطي النتائج:
3 5و
6 7 9 خمسة عشر 14 22 أحد عشر 19 17 24كومة المجموعة المتبقية سيعطي:
6 7 9 خمسة عشر 14 22 أحد عشر 19 17 24استخراج 6 وإضافة إلى القائمة الجديدة (مصفوفة) يعطي النتائج:
3 5 6و
7 9 خمسة عشر 14 22 أحد عشر 19 17 24كومة المجموعة المتبقية سيعطي:
7 9 أحد عشر 14 22 خمسة عشر 19 17 24استخراج 7 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7و
9 أحد عشر 14 22 خمسة عشر 19 17 24كومة المجموعة المتبقية يعطي:
9 أحد عشر 14 22 خمسة عشر 19 17 24استخراج 9 وإضافة إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9و
أحد عشر 14 22 خمسة عشر 19 17 24كومة المجموعة المتبقية يعطي:
أحد عشر 14 17 خمسة عشر 19 22 24استخراج 11 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشرو
14 17 خمسة عشر 19 22 24كومة المجموعة المتبقية سيعطي:
14 17 خمسة عشر 19 22 24استخراج 14 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14و
17 خمسة عشر 19 22 24كومة المجموعة المتبقية سيعطي:
خمسة عشر 17 19 22 24استخراج 15 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14 خمسة عشرو
17 19 22 24كومة المجموعة المتبقية سيعطي:
17 19 22 24استخراج 17 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14 خمسة عشر 17و
19 22 24كومة المجموعة المتبقية سيعطي:
19 22 24استخراج 19 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14 خمسة عشر 17 19و
22 24كومة المجموعة المتبقية يعطي:
22 24استخراج 22 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14 خمسة عشر 17 19 22و
24كومة المجموعة المتبقية يعطي:
24استخراج 24 وإضافته إلى القائمة الجديدة يعطي النتائج:
3 5 6 7 9 أحد عشر 14 خمسة عشر 17 19 22 24و
- - -صفيف الكومة فارغ الآن. جميع العناصر الموجودة في البداية موجودة الآن في المصفوفة الجديدة (القائمة) وفرزها.
خوارزمية Heapsort
على الرغم من أن القارئ ربما قرأ في الكتب المدرسية أن الفرز المتراكم يتكون من مرحلتين ، إلا أنه لا يزال من الممكن النظر إلى الفرز المتراكم على أنه يتكون من مرحلة واحدة ، والتي تتقلص بشكل متكرر من المصفوفة المحددة. مع ذلك ، فإن خوارزمية الفرز باستخدام heapsort هي كما يلي:
- كومة القائمة التي لم يتم فرزها.
- استخرج العنصر الأول من الكومة وضعه كعنصر أول في القائمة الجديدة.
- كومة القائمة المتبقية.
- استخرج العنصر الأول من الكومة الجديدة وضعه كعنصر تالي في القائمة الجديدة.
- كرر الخطوات السابقة بالترتيب حتى تصبح قائمة الكومة فارغة. في النهاية ، يتم فرز القائمة الجديدة.
زمن التعقيد المناسب
يتم استخدام نهج المرحلة الواحدة لتحديد مدى التعقيد الزمني لفرز الكومة. افترض أن هناك 8 عناصر لم يتم فرزها ليتم فرزها.
أقصى عدد ممكن من العمليات لتكديس ملف 8 العناصر 8 .ال أقصى عدد ممكن من العمليات لتكديس الباقي 7 العناصر 7 .
ال أقصى عدد ممكن من العمليات لتكديس الباقي 6 العناصر 6 .
ال أقصى عدد ممكن من العمليات لتكديس الباقي 5 العناصر 5 .
ال أقصى عدد ممكن من العمليات لتكديس الباقي 4 العناصر 4 .
ال أقصى عدد ممكن من العمليات لتكديس الباقي 3 العناصر 3 .
ال أقصى عدد ممكن من العمليات لتكديس الباقي اثنين العناصر اثنين .
ال أقصى عدد ممكن من العمليات لتكديس الباقي 1 العنصر 1 .
الحد الأقصى لعدد العمليات الممكنة هو:
8 + 7 + 6 + 5 + 4 + 3 + اثنين + 1 = 36متوسط عدد هذه العمليات هو:
36 / 8 = 4.5لاحظ أن الكومات الأربعة الأخيرة في الرسم التوضيحي السابق لم تتغير ، عند إزالة العنصر الأول. بعض الأكوام السابقة لم تتغير أيضًا عند إزالة العنصر الأول. مع ذلك ، يكون متوسط عدد العمليات الرئيسية (المبادلات) الأفضل هو 3 وليس 4.5. لذلك ، فإن متوسط إجمالي عدد العمليات الرئيسية الأفضل هو:
24 = 8 x 3=> 24 = 8 x سجل < الفرعية > اثنين < / الفرعية > 8
منذ تسجيل الدخول اثنين 8 = 3.
بشكل عام ، متوسط تعقيد وقت الحالة لفرز الكومة هو:
ا ( ن. log2n )حيث تعني النقطة الضرب و n هي N ، العدد الإجمالي للعناصر في القائمة (أي من القائمتين).
لاحظ أنه تم تجاهل عملية استخراج العنصر الأول. فيما يتعلق بموضوع تعقيد الوقت ، يتم تجاهل العمليات التي تستغرق أوقاتًا قصيرة نسبيًا.
الترميز في C ++
في مكتبة خوارزمية C ++ ، توجد دالة make_heap (). الصيغة هي:
قالب < صف دراسي RandomAccessIterator ، صف دراسي قارن >كونستكسبر فارغ جعل ( RandomAccessIterator أولاً ، RandomAccessIterator الأخير ، قارن comp ) ؛
يأخذ المكرر الذي يشير إلى العنصر الأول للمتجه باعتباره الوسيطة الأولى له ثم يشير المكرر إلى ما بعد نهاية المتجه مباشرةً باعتباره الوسيطة الأخيرة. بالنسبة للقائمة السابقة التي لم يتم فرزها ، سيتم استخدام بناء الجملة على النحو التالي للحصول على الحد الأدنى من الكومة:
المتجه < int > vtr = { 9 و 19 و 24 و 5 و 3 و أحد عشر و 14 و 22 و 7 و 6 و 17 و خمسة عشر } ؛المتجه < int > :: مكرر iterB = vtr. يبدأ ( ) ؛
المتجه < int > :: مكرر iterE = vtr. نهاية ( ) ؛
جعل ( iterB ، iterE ، أكبر < int > ( ) ) ؛
يغير هذا الرمز محتوى متجه إلى تكوين كومة أدنى. في متجهات C ++ التالية ، سيتم استخدام متجهين بدلاً من مصفوفتين.
لنسخ وإرجاع العنصر الأول من المتجه ، استخدم بناء الجملة المتجه:
كونستكسبر جبهة مرجعية ( ) ؛لإزالة العنصر الأول من المتجه وإلقائه بعيدًا ، استخدم صيغة المتجه:
كونستكسبر مكرر محو ( موضع المُثبِّت )لإضافة عنصر في الجزء الخلفي من المتجه (العنصر التالي) ، استخدم بناء الجملة المتجه:
كونستكسبر فارغ إدفع إلى الخلف ( مقدار ثابت تي & x ) ؛بداية البرنامج هي:
# تضمين# تضمين <الخوارزمية>
# تضمين <ناقل>
استخدام مساحة الاسم الأمراض المنقولة جنسيا ؛
يتم تضمين الخوارزمية ومكتبات المتجهات. التالي في البرنامج هو وظيفة heapsort () ، وهي:
فارغ نوع كومة ( المتجه < int > & قديم ، ناقلات < int > & جديد ) {إذا ( قديم بحجم ( ) > 0 ) {
المتجه < int > :: مكرر iterB = قديم يبدأ ( ) ؛
المتجه < int > :: مكرر iterE = قديم نهاية ( ) ؛
جعل ( iterB ، iterE ، أكبر < int > ( ) ) ؛
int التالي = قديم أمامي ( ) ؛
قديم محو ( iterB ) ؛
جديد إدفع إلى الخلف ( التالي ) ؛
نوع كومة ( oldV ، newV ) ؛
}
}
إنها دالة تكرارية. يستخدم الدالة make_heap () لمكتبة خوارزمية C ++. يستخرج مقطع الكود الثاني في تعريف الوظيفة العنصر الأول من المتجه القديم بعد بناء الكومة ويضيفه كعنصر تالي للمتجه الجديد. لاحظ أنه في تعريف الوظيفة ، تكون معلمات المتجه مراجع ، بينما يتم استدعاء الوظيفة بالمعرفات (الأسماء).
وظيفة C ++ الرئيسية المناسبة لهذا هي:
int رئيسي ( int أرجك شار ** أرجف ){
المتجه < int > قديم = { 9 و 19 و 24 و 5 و 3 و أحد عشر و 14 و 22 و 7 و 6 و 17 و خمسة عشر } ؛
المتجه < int > جديد ؛
نوع كومة ( oldV ، newV ) ؛
إلى عن على ( int أنا = 0 ؛ أنا < جديد بحجم ( ) ؛ أنا ++ ) {
كوت << جديد [ أنا ] << ' ؛
}
كوت << إندل ؛
إرجاع 0 ؛
}
الخرج هو:
3 5 6 7 9 أحد عشر 14 خمسة عشر 17 19 22 24مرتبة (بالكامل).
استنتاج
ناقش المقال بالتفصيل طبيعة ووظيفة Heap Sort المعروفة باسم Heapsort ، كخوارزمية فرز. تم تغطية ودعم Heapify Time Complexity و Heapsort Illustration و Heapsort كخوارزمية بواسطة الأمثلة. متوسط التعقيد الزمني لبرنامج كومة مكتوب جيدًا هو O (nlog (n))