1. لا بد لي من التحدث عن الأشجار الثنائية
لفهم الكومة ، يجب أولاً فهم الشجرة الثنائية. في علوم الكمبيوتر ، فإن الشجرة الثنائية هي بنية شجرة مع وجود اثنين من القطع الفرعية على الأكثر لكل عقدة. عادة ما تسمى القطع الفرعية "الشجرة الفرعية اليسرى" و "الشجرة الفرعية اليمنى". غالبًا ما تستخدم الأشجار الثنائية لتنفيذ أشجار البحث الثنائية والمواد الثنائية.
تحتوي كل عقدة لشجرة ثنائية على الأكثر فرعية (العقد بدرجات أكبر من 2). يمكن تقسيم الأشجار الفرعية للشجرة الثنائية إلى اليسار واليمين ، ولا يمكن عكس الأمر. الطبقة i -th من الشجرة الثنائية لها عقدة 2i - 1 على الأكثر ؛ الشجرة الثنائية مع عمق K لديها عقدة 2K - 1 على الأكثر ؛ بالنسبة لأي شجرة ثنائية T ، إذا كان عدد العقد الطرفية هو N0 وعدد العقد بدرجة 2 هو N2 ، N0 = N2 + 1.
هناك ثلاثة اختلافات رئيسية بين شجرة وشجرة ثنائية:
عدد العقد في الشجرة لا يقل عن 1 ، في حين يمكن أن يكون عدد العقد في الشجرة الثنائية 0.
لا يوجد حد على الحد الأقصى لدرجة العقد في الشجرة ، في حين أن الحد الأقصى لدرجة العقد في الشجرة الثنائية 2
لا يوجد فرق بين اليسار واليمين في العقد من الشجرة ، في حين لا يوجد فرق بين اليسار واليمين في العقد من شجرة ثنائية.
تنقسم الأشجار الثنائية إلى أشجار ثنائية كاملة وأشجار ثنائية كاملة.
شجرة ثنائية كاملة: شجرة ذات عمق K ولها عقدة 2K - 1 تسمى شجرة ثنائية كاملة
(شجرة ثنائية كاملة بعمق 3)
شجرة ثنائية كاملة: شجرة ثنائية مع عقد N مع العمق K. يطلق عليه شجرة ثنائية كاملة إذا وفقط إذا كان كل من العقد من العقد يتوافق مع عقدة مع أرقام تسلسل من 1 إلى N في شجرة ثنائية كاملة مع عمق K.
(شجرة ثنائية كاملة بعمق 3)
2. ما هي الكومة؟
يمكن اعتبار كومة (كومة ثنائية) شجرة ثنائية كاملة. تتمثل خاصية "ممتازة" لشجرة ثنائية كاملة في أنه ، باستثناء الطبقة السفلية ، تكون كل طبقة ممتلئة ، والتي تسمح بتمثيل الكومة بواسطة صفيف (عادة ما يتم تمثيل الأشجار الثنائية العامة العادية بواسطة قوائم مرتبطة كحاويات أساسية) ، وكل عقدة تتوافق مع عنصر في الصفيف.
يوضح الشكل التالي العلاقة بين كومة ومصفوفة
(العلاقة بين الكومة والمصفوفة)
بالنسبة للمنصب المفروض الأول من العقدة ، يمكن حسابها بسهولة لمرحلة العقدة الأصل والعقدة الفرعية لهذه العقدة:
الوالد (i) = floor (i/2) ، مجموعة الأصل العقدة من i
اليسار (i) = 2i ، مجموعة عقدة الطفل اليسرى من i
اليمين (i) = 2i + 1 ، مجموعة العقدة الصحيح للطفل من i
هناك عمومًا نوعان من النواة الثنائية: أكبر كومة وأصغر كومة.
أقصى كومة:
تظهر قيمة العنصر القصوى في الحد الأقصى للكومة في عقدة الجذر (أعلى الكومة)
قيمة العنصر لكل عقدة الوالدين في الكومة أكبر من أو تساوي عقدة طفلها (إذا كانت موجودة)
(أقصى كومة)
الحد الأدنى للكومة:
تظهر قيمة العنصر الدنيا في الحد الأدنى للكومة في عقدة الجذر (أعلى الكومة)
قيمة العنصر لكل عقدة الوالدين في الكومة أقل من أو تساوي عقدة طفلها (إذا كانت موجودة)
(الحد الأدنى المكدس)
3. مبدأ فرز الكومة
تتمثل فرز الكومة في إخراج الحد الأقصى لعدد في الجزء العلوي من الحد الأقصى للكومة ، والاستمرار في ضبط الكومة المتبقية إلى أقصى كومة ، وإخراج الحد الأقصى لعدد في الجزء العلوي من الكومة مرة أخرى. تستمر هذه العملية حتى يكون هناك رقم واحد متبقي فقط. حدد العمليات التالية في الكومة:
Max-Heapify: اضبط عقدة النهاية للكومة بحيث تكون العقدة الفرعية أصغر دائمًا من العقدة الأصل
قم بإنشاء أقصى كومة (Build-Max-Heap): أعد ترتيب جميع بيانات الكومة لجعلها أقصى كومة
كومة SORT: قم بإزالة عقدة الجذر للبيانات الأولى وأداء التشغيل العودية لتحقيق أقصى قدر من ضبط الكومة
قبل مواصلة المناقشة التالية ، إحدى القضايا التي يجب الإشارة إليها هي: المصفوفات كلها قائمة على الصفر ، مما يعني أن نموذج بنية بيانات الكومة لدينا سيتغير.
(قائم على الصفر)
في المقابل ، يجب أيضًا تعديل العديد من صيغ الحساب وفقًا لذلك:
الوالد (i) = floor ((I-1)/2) ، مجموعة الأصل العقدة لـ i
اليسار (i) = 2i + 1 ، مجموعة عقدة الطفل اليسرى من i
اليمين (i) = 2 (i + 1) ، تراكب عقدة الطفل الصحيح لـ i
تتمثل وظيفة تعديل Max Heap (MaxHeapify) في الحفاظ على خصائص أكبر كومة وهي الروتين الفرعي الأساسي لإنشاء أكبر كومة. يتم عرض عملية التشغيل في الشكل:
(Max-Heapify)
نظرًا لأن الكومة لا تزال تنتهك طبيعة الكومة بعد تعديل واحد ، فإن الاختبار العودية مطلوب بحيث يرضي الكومة بأكملها طبيعة الكومة. يمكن التعبير عنها في JavaScript على النحو التالي:
/** * تحقق من الفهرس والحفاظ على الحد الأقصى لخصائص الكومة * * @array * * فهرس البدء لفحص @index * * heapsize size * **/function maxHeapify (صفيف ، فهرس ، تكثيف) {var imax = index ، ileft = 2 * index + 1 ، iright = 2 * (index + 1) ؛ if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft ؛ } if (iright <heapsize && array [imax] <array [iright]) {imax = iright ؛ } if (imax! = index) {swap (Array ، Imax ، index) ؛ maxheapify (صفيف ، imax ، الكثافة) ؛ // تعديل متكرر}} تبديل الوظيفة (صفيف ، i ، j) {var temp = array [i] ؛ صفيف [i] = صفيف [j] ؛ صفيف [j] = temp ؛}بشكل عام ، يتم استخدام العودية بشكل أساسي في طريقة التقسيم والعلاج ، وليس هناك حاجة للتقسيم والعلاج هنا. علاوة على ذلك ، تتطلب المكالمات العودية الضغط على المكدس/المقاصة ، والتي لها عيب طفيف في الأداء مقارنة بالتكرار. بالطبع ، يمكن تجاهل هذا وفقًا لقاعدة 20/80. ولكن إذا كنت تعتقد أن استخدام العودية سيجعلك تشعر بعدم الارتياح ، فيمكنك أيضًا استخدام التكرار ، مثل ما يلي:
/** * تحقق من الفهرس والحفاظ على الحد الأقصى لخصائص الكومة * * @array * * فهرس البدء للتحقق من @ بينما (صحيح) {imax = index ؛ ileft = 2 * index + 1 ؛ Iright = 2 * (الفهرس + 1) ؛ if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft ؛ } if (iright <heapsize && array [imax] <array [iright]) {imax = iright ؛ } if (imax! = index) {swap (Array ، Imax ، index) ؛ الفهرس = IMAX ؛ } آخر {break ؛ }}} تبديل الدالة (صفيف ، i ، j) {var temp = array [i] ؛ صفيف [i] = صفيف [j] ؛ صفيف [j] = temp ؛}الغرض من إنشاء أقصى كومة (Build-Max-Heap) هو تحويل صفيف إلى كومة أقصى ، وقبول معلمتين من الصفيف وحجم الكومة. سيقوم Build-Max-Heap بالاتصال Max-Heapify من أسفل إلى أعلى لتحويل الصفيف وإنشاء أقصى كومة. نظرًا لأن Max-Heapify يمكن أن يضمن أن العقد بعد الاشتراك ، أفي بخصائص أكبر كومة ، يمكن للدعوة من أسفل إلى أقصى إلى Max-Heapify الحفاظ على هذه الخاصية أثناء عملية التحول. إذا كان عنصر رقم الكومة الأقصى هو N ، فإن إنشاء Heap Confer Confer Max-Heapify بالتسلسل من Parent (N). العملية كما يلي:
الوصف كما يلي في جافا سكريبت:
وظيفة buildMaxHeap (صفيف ، تكثيف) {var i ، iParent = Math.floor ((Heapsize - 1) / 2) ؛ لـ (i = iParent ؛ i> = 0 ؛ i--) {maxHeapify (Array ، i ، Heapsize) ؛ }}كومة sort هي خوارزمية الواجهة لفرز الكومة. يستدعي Heap-Sort First Build-Max-Heap لتحويل الصفيف إلى أقصى كومة ، ثم يقوم بتبادل العناصر العلوية والسفلية للكومة ، ثم يرتفع القاع ، وأخيراً يدعو Max-Heapify للحفاظ على أقصى خصائص الكومة. نظرًا لأن العنصر العلوي من الكومة يجب أن يكون أكبر عنصر في الكومة ، وبعد عملية واحدة ، يتم فصل العنصر الأكبر الموجود في الكومة عن الكومة عن الكومة ، وبعد متكرر N-1 ، يتم ترتيب الصفيف. العملية برمتها على النحو التالي:
الوصف كما يلي في جافا سكريبت:
وظيفة Hepsort (صفيف ، تكثيف) {buildMaxHeap (صفيف ، تكثيف) ؛ لـ (int i = heapsize-1 ؛ i> 0 ؛ i--) {swap (array ، 0 ، i) ؛ Maxheapify (Array ، 0 ، i) ؛ }}4. تنفيذ لغة جافا سكريبت
أخيرًا ، قم بتنظيم ما سبق في رمز JavaScript الكامل على النحو التالي:
دالة Hepsort (Array) {Swap (Array ، I ، J) {var temp = array [i] ؛ صفيف [i] = صفيف [j] ؛ صفيف [j] = temp ؛ } وظيفة maxheapify (صفيف ، فهرس ، تكثيف) {var imax ، ileft ، iright ؛ بينما (صحيح) {imax = index ؛ ileft = 2 * index + 1 ؛ Iright = 2 * (الفهرس + 1) ؛ if (ileft <heapsize && array [index] <array [ileft]) {imax = ileft ؛ } if (iright <heapsize && array [imax] <array [iright]) {imax = iright ؛ } if (imax! = index) {swap (Array ، Imax ، index) ؛ الفهرس = IMAX ؛ } آخر {break ؛ }}} وظيفة buildMaxHeap (Array) {var i ، iParent = math.floor (Array.length / 2) - 1 ؛ لـ (i = iParent ؛ i> = 0 ؛ i--) {maxHeapify (Array ، i ، array.length) ؛ }} function sort (Array) {buildMaxHeap (Array) ؛ لـ (var i = array.length-1 ؛ i> 0 ؛ i--) {swap (Array ، 0 ، i) ؛ Maxheapify (Array ، 0 ، i) ؛ } صفيف الإرجاع ؛ } فرز الإرجاع (صفيف) ؛}5. تطبيق خوارزمية فرز الكومة
(1) أداء الخوارزمية/التعقيد
يعد التعقيد الزمني لفرز الكومة مستقرًا للغاية (يمكننا أن نرى أنه ليس حساسًا لبيانات الإدخال) ، وهو تعقيد O (NN) ، والحالة الأفضل هي نفس الحالة.
ومع ذلك ، يختلف تعقيدها المكاني وفقًا للتنفيذ. ما سبق يناقش تعقيدين مشتركين: O (N) و O (1). بناءً على مبدأ توفير مساحة ، أوصي طريقة التعقيد O (1).
(2) استقرار الخوارزمية
هناك عدد كبير من عمليات التصفية والنقل في فرز الكومة ، والتي تنتمي إلى خوارزمية فرز غير مستقرة.
(3) السيناريو المطبق خوارزمية
سوف يتحمل فرز الكومة النفقات العامة الكبيرة نسبيًا في عملية بناء الكومة وتعديل الكومة ، ولا ينطبق عندما يكون هناك عدد قليل من العناصر. ومع ذلك ، عندما يكون هناك العديد من العناصر ، فإنه لا يزال خيارًا جيدًا. خاصة عند حل مشكلات مثل "عدد الأعلى n الكبير" ، فهي تقريبًا الخوارزمية المفضلة.