كومة هي بنية مهمة في بنية البيانات. بعد فهم مفهوم "كومة" وتشغيله ، يمكنك إتقان فرز الكومة بسرعة.
مفهوم الكومة
كومة هي شجرة ثنائية كاملة. إذا لم تكن قيم جميع العقد من شجرة ثنائية تمامًا أصغر من أطفالهم ، فهي تسمى كومة جذر كبيرة (أو كومة أعلى كبيرة) ؛ إذا لم تكن قيم جميع العقد أكبر من أطفالها ، فسيطلق عليها كومة جذر صغيرة (أو كومة أعلى صغيرة).
في صفيف (تخزين عقدة الجذر في الرقم الفردي 0) ، من السهل الحصول على المعادلة التالية (هاتان المعادلتان مهمتان للغاية):
1. العقدة مع التراكمية هي I ، وإحداثيات العقدة الأصل هي (I-1)/2 ؛
2. العقدة مع التراكمية هي i ، وإحداثيات عقدة الطفل اليسرى هي 2*i+1 ، والعقدة الطفل الأيمن هي 2*i+2.
إنشاء الكومة وصيانتها
يمكن للكومة دعم عمليات متعددة ، لكننا الآن نهتم فقط بقضيتين:
1. إعطاء صفيف غير مرتبة ، كيف تبنيها كوسيلة؟
2. بعد حذف العنصر العلوي من الكومة ، كيفية ضبط التكوين على كومة جديدة؟
دعونا نلقي نظرة على السؤال الثاني أولاً. لنفترض أن لدينا بالفعل كومة جذر كبيرة جاهزة. الآن نقوم بحذف عنصر الجذر ، لكننا لا ننقل العناصر الأخرى. فكر فيما حدث: عنصر الجذر فارغ ، لكن العناصر الأخرى لا تزال تحافظ على خصائص الكومة. يمكننا نقل العنصر الأخير (اسم الرمز أ) إلى موضع عنصر الجذر. إذا لم تكن حالة خاصة ، يتم تدمير خصائص الكومة. ولكن هذا ببساطة لأن A أصغر من أحد عناصرها. لذلك ، يمكننا تبديل A وهذا العنصر الطفل لوضعه. إذا كان A أكبر من جميع عناصرها الفرعية ، يتم ضبط الكومة ؛ بخلاف ذلك ، كرر العملية أعلاه ، ويستمر العنصر A في "غرق" في بنية الشجرة حتى يكون مناسبًا ، ويعيد الصفيف خصائص الكومة. تسمى العملية أعلاه بشكل عام "الفحص" ، والاتجاه من الواضح من أعلى إلى أسفل.
هذا صحيح عند حذف عنصر ، وكذلك إدخال عنصر جديد. الفرق هو أننا نضع العنصر الجديد في النهاية ثم نقارنه بالعقدة الأم ، أي تصفيةه من أسفل إلى أعلى.
لذلك ، كيف تحل المشكلة الأولى؟
يتم تصفية العديد من الكتب الموجودة في هياكل البيانات التي قرأتها من العقدة الأولى غير الأوراق حتى يتم ترشيح عنصر الجذر. تسمى هذه الطريقة "طريقة التصفية" ، والتي تتطلب عناصر تصفية حلقة N/2.
ولكن يمكننا أيضًا أن نتعلم من فكرة "إنشاء شيء من لا شيء". يمكننا أن نعتبر العنصر الأول كومة ثم إضافة عناصر جديدة باستمرار. تسمى هذه الطريقة "إدراج طريقة" ، والتي تتطلب إدخال حلقة لعناصر (N-1).
نظرًا لأن طريقة الترشيح وطريقة الإدراج مختلفة ، فإن الأمواح التي تنشئها تختلف عمومًا لنفس البيانات.
بعد فهم تقريبي للكومة ، يعد فرز الكومة أمرًا طبيعيًا.
نظرة عامة على الخوارزمية
نحن بحاجة إلى تسلسل تصاعدي ، ماذا يجب أن نفعل؟ يمكننا بناء الحد الأدنى من الكومة ثم إخراج عنصر الجذر في كل مرة. ومع ذلك ، تتطلب هذه الطريقة مساحة إضافية (وإلا فإنها ستؤدي إلى الكثير من حركة العناصر ، وسوف يرتفع تعقيدها إلى O (n^2)). ماذا لو كنا بحاجة إلى الفرز في مكان (أي ، لا يوجد أي تعقيد الفضاء o (ن)؟
هناك طريقة. يمكننا إنشاء الحد الأقصى للكومة ، ثم نخرج القيمة القصوى في الموضع الأخير ، والقيمة القصوى الثانية في الموضع الأخير ... نظرًا لأن الحد الأقصى للإخراج العنصر في كل مرة سيقوم بتحرير المساحة الأولى ، يمكننا فقط وضع مثل هذا العنصر دون الحاجة إلى مساحة إضافية. فكرة جميلة جدا ، أليس كذلك؟
الفئة العامة Heapsort {public static void main (string [] args) {int [] arr = {50 ، 10 ، 90 ، 30 ، 70 ، 40 ، 80 ، 60 ، 20} ؛ System.out.println ("قبل الفرز:") ؛ لـ (int i = 0 ؛ i <arr.length ؛ i ++) {system.out.print (arr [i]+"") ؛ } // كومة فرز الكثافة (arr) ؛ system.out.println () ؛ System.out.println ("بعد الفرز:") ؛ لـ (int i = 0 ؛ i <arr.length ؛ i ++) {system.out.print (arr [i]+"") ؛ }} / *** sort heap* / private static void hepsort (int [] arr) {// إنشاء التسلسل المراد فرزه في كومة قمة كبيرة لـ (int i = arr.length / 2 ؛ } // تبديل عقدة الجذر تدريجياً لكل قيمة الحد الأقصى مع العنصر النهائي ، وضبط الشجرة الثنائية لجعلها كومة أعلى كبيرة لـ (int i = arr.length-1 ؛ i> 0 ؛ i--) {swap (arr ، 0 ، i) ؛ // تبادل السجل الأعلى للكومة مع السجل الأخير من الكلية اللاحقة غير المصنفة حاليًا (ARR ، 0 ، i) ؛ // بعد التبادل ، من الضروري إعادة فحص ما إذا كانت الكومة تلتقي بكومة كبيرة. إذا لم يلتقي ، يجب تعديله} / *** عملية بناء الكومة* param arr التي يجب فرزها* param i عدد عقدة الجذر للكومة التي يجب بناؤها* param n بطول المصفوفة* / private static void -just (int [] int i ، int n) {int n) أيها الأب لـ (الأب = arr [i] ؛ LeftChild (i) <n ؛ i = child) {child = LeftChild (i) ؛ // إذا كان الشجرة الفرعية اليسرى أصغر من الشجرة الفرعية اليمنى ، فأنت بحاجة إلى مقارنة الشجرة الفرعية اليمنى مع العقدة الأصل إذا (الطفل! = n - 1 && arr [child] <arr [child+1]) {child ++ ؛ // قم بزيادة الرقم التسلسلي بمقدار 1 ، مشيرًا إلى الشجرة الفرعية اليمنى} // إذا كانت العقدة الأصل أصغر من العقدة الفرعية ، فأنت بحاجة إلى تبادل إذا (الأب <arg [child]) {arr [i] = arr [child] ؛ } آخر {break ؛ // لم يتم تدمير بنية الكومة العلوية الكبيرة ، ولا يوجد أي تعديل مطلوب}} arr [i] = الأب ؛ } // الحصول على عقدة الطفل اليسرى ثابتة int intchild (int i) {return 2 * i + 1 ؛ }. arr [index1] = arr [index2] ؛ arr [index2] = tmp ؛ }}