ملخص
فرز الكومة هو فرز اختيار الأشجار ، وهو تحسن فعال في فرز الاختيار المباشر.
يتم تعريف الكومة على النحو التالي: سلسلة من العناصر n (K1 ، K2 ، ... ، KN) ، إذا وفقط إذا كان راضيا:
يطلق عليه كومة في ذلك الوقت. كما يتضح من تعريف الكومة ، يجب أن يكون العنصر العلوي من الكومة (أي العنصر الأول) هو أصغر عنصر (كومة أعلى صغيرة) أو أكبر عنصر (كومة أعلى كبيرة).
إذا تم تخزين كومة في صفيف أحادي البعد ، فإن الكومة تتوافق مع شجرة ثنائية تمامًا ، وقيم جميع العقد غير الأوراق (العقد مع الأطفال) ليست أكبر من (أو لا تقل عن) قيم أطفالهم ، وقيم عقدة الجذر (العنصر العلوي في الكومة) هي أصغر (أو الأكبر).
(أ) تسلسل كومة كبير كبير: (96 ، 83 ، 27 ، 38 ، 11 ، 09)
(ب) تسلسل كومة صغير صغير: (12 ، 36 ، 24 ، 85 ، 47 ، 30 ، 53 ، 91)
في البداية ، يعتبر تسلسل الأرقام N التي سيتم فرزها بمثابة شجرة ثنائية مخزنة بالتتابع (شجرة تخزين صفيف أحادية البعد) ، وضبط ترتيب التخزين الخاص بها لجعله كومة ، وإخراج العنصر العلوي من الكومة للحصول على أصغر (أو أكبر عنصر) في العناصر N. ثم قم بتعديل عناصر N-1 المتبقية لتصبح كومة ، وإخراج العنصر العلوي من الكومة ، والحصول على العنصر الذي هو الثاني الصغير (أو الثاني الكبير) بين العناصر N. وهكذا حتى تحصل أخيرًا على تسلسل مرتبة مع العقد N. استدعاء هذه العملية الكومة.
الخطوات والأمثلة
هناك مشكلتان للحل في تنفيذ فرز الكومة:
(1) كيفية بناء أرقام N ليتم فرزها في أكوام ؛
(2) بعد إخراج العنصر العلوي من الكومة ، كيفية ضبط عناصر N-1 المتبقية لجعله كومة جديدة.
بناء طريقة كومة (كومة أعلى صغيرة):
عملية بناء كومة للتسلسل الأولي هي عملية الفحص المتكرر.
شجرة ثنائية كاملة من العقد n ، ثم العقدة الأخيرة هي الشجرة الفرعية للعقدة N/2th.
يبدأ المرشح مع الشجرة الفرعية مع العقدة N/2th حيث الجذر (N/2 هي العقدة الأخيرة مع الشجرة الفرعية) ، بحيث تصبح الشجرة الفرعية كومة.
بعد ذلك ، قم بتصفية الأشكال الفرعية مع كل عقدة كجذر في التسلسل للأمام لجعله كومة حتى عقدة الجذر.
كما هو مبين في الشكل ، فإن التسلسل المضطرب للعملية الأولية لبناء كومة: (49 ، 38 ، 65 ، 97 ، 76 ، 13 ، 27 ، 49)
(أ) التسلسل غير المرتبة ، الشجرة الثنائية الأولية ، 97 (8/2 = 4 عقدة) هي العقدة الأصل للعقدة الأخيرة (49).
(ب) 97> = 49 ، استبدل الموضع ، ثم قم بتصفية العقدة السابقة 65 من N/2.
(ج) 13 <= 27 و 65> = 13 ، استبدل مواضع 65 و 13 ، ثم استبدل 38 (كلاهما أكبر منه ، لا توجد عملية مطلوبة) ، مرشح 49.
(د) 13 <= 38 و 49> = 13 ، استبدل مواضع 49 و 13 ، 49> = 27 ، استبدل مواضع 49 و 27.
(هـ) أخيرًا الحصول على كومة ، 13 هو الحد الأدنى للرقم الذي نحصل عليه.
طرق لضبط الكومة (كومة أعلى صغيرة):
يتم توفير كومة من عناصر m. بعد إخراج العناصر العليا من الكومة ، يتم ترك عناصر M-1. يتم تغذية العنصر السفلي للكومة إلى أعلى الكومة ، ويتم تدمير الكومة ، لأن عقدة الجذر لا تفي بخصائص الكومة.
تبادل عقدة الجذر مع عناصر أصغر في القطع الفرعية اليسرى والأيمن.
إذا تم تبادلها مع الشجرة الفرعية اليسرى: إذا كان كومة الشجرة الفرعية اليسرى تالفة ، فكرس طريقة (2).
إذا تم تبادلها مع الشجرة الفرعية اليمنى ، كرر الطريقة (2) إذا تم تدمير كومة الشجرة الفرعية اليمنى.
استمر في إجراء عملية التبادل أعلاه على الأشكال الفرعية التي لا تفي بخصائص الكومة حتى يتم بناء العقد الورقية ويتم بناء الكومة.
لضبط الكومة ، تحتاج فقط إلى النظر في العقد التالفة ، ولا تحتاج العقد الأخرى إلى تعديلها.
تنفيذ الكود (Java)
قم بتشغيل الكود وقارن التعليقات مع الخطوات المثال أعلاه للمقارنة.
package com.coder4j.main ؛ heapsort من الفئة العامة { / ** * اضبط مع كومة قمة صغيرة (والنتيجة من كبيرة إلى صغيرة بعد الفرز) * * صفيف param هو صفيف الكومة المراد تعديله * @param s هو موضع intray int ، TMP = صفيف [s] ؛ int child = 2 * s + 1 ؛ // موضع عقدة الطفل الأيسر. على الرغم من أن (الطفل <الطول) {// child + 1 هو الطفل المناسب الذي يقوم حاليًا بضبط العقدة // إذا كان هناك طفل مناسب وأصغر من الطفل الأيسر ، فاستخدم الطفل الأيمن للمقارنة مع العقدة ، وإلا استخدم الطفل الأيسر إذا (الطفل + 1 <الطول && صفيف [طفل]> [طفل + 1]) {طفل ++ ؛ } system.out.println ("سيكون مع صفيف الطفل [" + child + "] =" + Array [child] + "Compare") ؛ // إذا كان الطفل الأصغر أصغر من هذه العقدة if (Array [s]> Array [child]) {system.out.println ("الطفل أصغر منه ، وضع المبادلة") ؛ صفيف [s] = صفيف [طفل] ؛ // حرك الطفل الأصغر لأعلى واستبدل العقدة الحالية المراد تعديلها s = child ؛ // حرك العقدة المعدلة إلى الموضع الأصلي لصفيف الطفل الأصغر [الطفل] = tmp ؛ child = 2 * s + 1 ؛ // استمر في الحكم على ما إذا كانت العقدة المراد تعديلها تحتاج إلى تعديلها إذا (child> = length) {system.out.println ("لا يوجد أطفال ، انتهى التعديل") ؛ } آخر {system.out.println ("تابع المقارنة مع الطفل الجديد") ؛ } // يكمل؛ } آخر {system.out.println ("الأطفال أقدم منهم ، انتهى التعديل") ؛ استراحة ؛ // // العقدة الحالية المراد ضبطها أصغر من أطفالها الأيسر واليمين ، ولا يلزم ضبطها ، والخروج مباشرة}}/ ** *. examejustb (int [] array ، int s ، int) {int tmp = array [s] ؛ int child = 2 * s + 1 ؛ // موضع عقدة الطفل الأيسر. على الرغم من أن (الطفل <الطول) {// child + 1 هو الطفل المناسب الذي يقوم حاليًا بضبط العقدة // إذا كان هناك طفل مناسب وكان أكبر من الطفل الأيسر ، فاستخدم الطفل الأيمن للمقارنة مع العقدة ، وإلا استخدم الطفل الأيسر إذا (الطفل + 1 <length && Array [child] [child + 1]) {child ++ ؛ } system.out.println ("سيكون مع صفيف الطفل [" + child + "] =" + Array [child] + "Compare") ؛ // إذا كان الطفل الأقدم أكبر من هذه العقدة إذا كان (Array [s] <array [child]) {system.out.println ("الطفل أكبر منه ، موضع المبادلة") ؛ صفيف [s] = صفيف [طفل] ؛ // حرك الطفل الأقدم لأعلى واستبدل العقدة الحالية المراد تعديلها s = child ؛ // حرك العقدة المعدلة إلى الموضع الأصلي لمجموعة الطفل الأقدم [child] = tmp ؛ child = 2 * s + 1 ؛ // استمر في الحكم على ما إذا كانت العقدة المراد تعديلها تحتاج إلى تعديل إذا (child> = length) {system.out.println ("لا يوجد أطفال ، انتهى التعديل") ؛ } آخر {system.out.println ("تابع المقارنة مع الطفل الجديد") ؛ } // يكمل؛ } آخر {system.out.println ("الأطفال أصغر منهم ، انتهى التعديل") ؛ كسر ؛ // العقدة الحالية المراد تعديلها أكبر من أطفالها الأيسر واليمين ، والخروج مباشرة بدون تعديل}}}/ ** * * خوارزمية فرز الكومة * * @param * param عكسية صحيح في الترتيب العكسي ، خطأ في الترتيب الإيجابي */ الأثرية الثابتة العامة) / 2 ، وذلك لضبط كل عقدة لأعلى لتتوافق مع نظام الكومة. لـ (int i = (array.length-1) / 2 ؛ i> = 0 ؛ i--) {if (عكسي) {thepadjusts (Array ، i ، array.length) ؛ } آخر {heapadjustb (Array ، i ، array.length) ؛ }} system.out.println ("نهاية الكومة الأولية") ؛ لـ (int i = array.length-1 ؛ i> 0 ؛ i--) {// تبديل العنصر العلوي الكومة h [0] والعنصر الأخير في الكومة int tmp = array [i] ؛ صفيف [i] = صفيف [0] ؛ صفيف [0] = TMP ؛ // بعد كل مبادلة العنصر العلوي للكومة والعنصر الأخير في الكومة ، يجب تعديل الكومة إذا (عكسي) {thepadjusts (Array ، 0 ، i) ؛ } آخر {heapadjustb (صفيف ، 0 ، i) ؛ }}} الفراغ الثابت العام (سلسلة [] args) {int [] array = {49 ، 38 ، 65 ، 97 ، 76 ، 13 ، 27 ، 49} ؛ Heapsort (صفيف ، خطأ) ؛ لـ (int i: array) {system.out.print (i + "") ؛ }}}نتائج التشغيل:
العقدة المراد ضبطها في بداية الكومة الأولية هي: الصفيف [3] = 97 سيكون الطفل أصغر مع صفيف الطفل [7] = 49 = 38 يكون الطفل أكبر مع صفيف الطفل [3] = 49 يكون الطفل أكبر مع صفيف الطفل [0] = 49 يكون الطفل أصغر مع صفيف الطفل [2] = 13 يكون الطفل أصغر مع صفيف الطفل [6] = 27 أن الطفل أصغر من موضع التبادل ، ولا يوجد طفل في موضع التبادل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 97 الطفل أصغر من الطفل. الطفل أصغر من الطفل. يستمر موقف التبادل في المقارنة مع الطفل الجديد. الطفل هو صفيف [6] = 49 الطفل أصغر من موضع التبادل ، ولا يوجد طفل في وضع التبادل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 97 الطفل أصغر من الطفل. الطفل أصغر من الطفل. الطفل أصغر من الطفل. الطفل هو صفيف [1] = 38 الطفل أصغر من الطفل. الطفل هو صفيف [3] = 49 الطفل أصغر من الطفل. الطفل أصغر من موقف التبادل. العقدة المراد تعديلها بعد التعديل هي: الصفيف [0] = 65 أن الطفل هو صفيف [1] = 49 أن الطفل أصغر من الطفل ، ويستمر مقارنة وضع التبادل مع الطفل الجديد. سيكون الطفل أكبر من الطفل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 76 الطفل أكبر من الطفل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 76 الطفل أصغر من الطفل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 49 الطفل أصغر من الطفل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 97 الطفل أصغر من الطفل. العقدة المراد ضبطها بعد التعديل هي: صفيف [0] = 97 76 65 49 49 38 27 13
ملاحظة: الفرق بين فرز الكومة وفرز الإدراج المباشر
في ترتيب التحديد المباشر ، من أجل تحديد السجل مع أصغر كلمة رئيسية من R [1..n] ، يجب إجراء مقارنة N-1 ، ثم حدد السجل مع أصغر كلمة رئيسية في R [2..N] ، يجب إجراء مقارنات N-2. في الواقع ، في المقارنات N-2 التالية ، قد تم إجراء العديد من المقارنات في المقارنات N-1 السابقة ، ولكن نظرًا لم يتم الاحتفاظ بنتائج المقارنة هذه بالترتيب السابق ، فقد تم تكرار عمليات المقارنة هذه خلال الطلب التالي.
يمكن أن يوفر فرز الكومة جزءًا من نتائج المقارنة من خلال بنية شجرة ، مما يمكن أن يقلل من عدد المقارنات.