يشرح رمز Java كمثال على الخصائص والعمليات الأساسية وطرق الفرز للأكوام

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

كما يتضح في الشكل أعلاه ، يمكن ترتيب العقد من شجرة ثنائية تمامًا بالترتيب من رقم العقدة الجذر 1 ، المقابلة للفهرس في المصفوفة A (لاحظ أن العاطفة هنا تبدأ من 1). بالنظر إلى العقدة i ، يمكننا بسهولة الحصول على طفلها الأيسر هو 2i ، والطفل الأيمن هو 2i+1 ، والعقدة الوالدة هي I/2

العمليات الأساسية للكومة
هناك عمليتان أساسيتان للكومة (انظر الحد الأدنى للكومة على سبيل المثال أدناه):
إدراج العنصر K: أضف K مباشرةً إلى نهاية الصفيف ، ثم قم بالفقاعات لضبط الكومة. عملية الفقاعات: قارن العنصر المراد تعديله مع العقدة الأم ، وإذا كانت أكبر من العقدة الأم ، فقم بتبادلها حتى تتم استعادة خصائص الكومة.
استخراج معظم القيمة: معظم القيمة هي عنصر الجذر. ثم قم بحذفه ، واترك عنصر الجذر = عنصر عقدة الورقة الأخير ، ثم فقاعة من عنصر الجذر لضبط الكومة. Bubble Down Operation: في كل مرة ، يجب عليك تحديد أصغر عقدة للأطفال من العقد الثلاثة لضبط العقدة ، التي لديها الأطفال الأيسر واليمين للتبادل (إذا كان الأصغر ، فهي لا تحتاج إلى تبادل نفسها) ، حتى تتم استعادة خصائص الكومة.
في الممارسة العملية ، غالبًا ما يكون من الضروري إنشاء صفيف غير مرتبة يحتوي على عناصر N في أكوام. سيوضح المُنشئ في فئة الكومة أدناه كيفية بناء كومة من خلال تعديل فقاعة _bubbledown. الكومة هي في الأساس شجرة ثنائية تمامًا ، وارتفاع الشجرة دائمًا lognlog⁡n. تتمثل التشغيل المستهلكة للوقت لكل عملية أساسية في التغلب على خصائص الكومة والتكيف لتلبية خصائص الكومة ، وبالتالي فإن تعقيد الوقت الخاص بهم هو O (nlogn) o (nlog⁡n).
مثال جافا:

 // float public void swim (int k) {بينما (k/2> = 1 && less (pq [k/2] ، pq [k])) {tix (pq ، k/2 ، k) ؛ k = k/2 ؛ }} // sink private void sint () {int k = 1 ؛ بينما (2*k <n) {int j = 2*k ؛ if (أقل (pq [j] ، pq [j+1])) j ++ ؛ إذا (أقل (pq [k] ، pq [j])) tail (pq ، k ، j) ؛ استراحة أخرى k = j ؛ }}

مبدأ تنفيذ فرز الكومة
ينقسم إلى خطوتين:
1. ترتيب المصفوفات بترتيب كومة ثنائية
2. قم بتغيير موضع عقدة الجذر والعقدة الأخيرة ، ثم تغرق عقدة الجذر.

ينجز:
ربما يختلف الكود الخاص بي قليلاً عن الرسوم المتحركة أعلاه ، لكن المبادئ الأساسية متشابهة.

 يمتد Heapsort الطبقة العامة Basesort {private int n ؛ Override public void sort (مماثلة [] a) {n = A.Length-1 ؛ int k = n/2 ؛ بينما (k> = 1) {sint (a ، k) ؛ ك- ؛ } k = 1 ؛ بينما (k <= n) {tix (a ، k ، n--) ؛ بالوعة (أ ، ك) ؛ }}}