خوارزمية جافا تبدأ بمثال فرز الكومة

لتعلم فرز الكومة ، يجب أولاً فهم مفهوم الكومة. يمكن أن يكون تقريبيًا كطريقة تخزين الصفيف كشجرة ثنائية تمامًا. ولكن هناك خصائص أخرى معه ، والتي تشبه أشجار الفرز الثنائية. هناك اختلافات بين أكبر كومة وأصغر كومة. من عقدة طفلها. يستخدم فرز الكومة عمومًا أكبر كومة ، في حين أن أصغر كومة يمكنها إنشاء قائمة انتظار ذات أولوية. هناك طريقة في الكومة المستخدمة للحفاظ على خصائص الكومة ، وهي طريقة Maxheap في الكود أدناه. الصفيف ، والمعلمة الثانية هي ضبط الكومة. عناصر صالحة مخزنة بالفعل في الكومة. ربما يكون طول الصفيف هو عدد العناصر المخزنة فعليًا في الكومة ، ولكن ليس بالضرورة جميع البيانات التي نحتاجها لإنشاء أقصى كومة. يقول مقدمة الخوارزمية أن العقدة الفرعية اليسرى هي 2xi ، لكن الصفيف الخاص بنا من 0 ، وبالتالي فإن العقدة الفرعية اليسرى تصبح 2xi+1. 2 هو ، أن العقد الفرعية لهذه النقاط هي جميع العقد الأوراق ، لذلك نحن نبني أقصى كومة عن طريق فرزها من أسفل إلى أعلى. تأكد من أن جميع العقد في كومةنا تلبي أقصى خصائص كومة. أخيرًا ، يهدف فرز الكومة إلى إخراج العقدة الأولى ، وفرز العقد المتبقية مرة أخرى ، ثم أخرج عقدة الجذر. هذا يضمن أنه في كل مرة نخرجها ، فهذا أقصى قيمة.

نسخة الكود كما يلي:

الطبقة العامة Heapsort {

private int getleft (int i) {

إرجاع 2*i+1 ؛

}

private int getright (int i) {

إرجاع 2*i+2 ؛

}

public void maxheap (int [] heap ، int loc ، int size) {

int l = getleft (loc) ؛

int r = getRight (loc) ؛

int أكبر = loc ؛

if (l <size && heap [l]> heap [loc]) {

أكبر = ل ؛

}

if (r <size && heap [r]> heap [الأكبر]) {

أكبر = ص ؛

}

إذا (الأكبر! = loc) {

int cache = heap [loc] ؛

كومة [loc] = كومة [أكبر] ؛

كومة [أكبر] = ذاكرة التخزين المؤقت ؛

Maxheap (كومة ، كبيرة ، حجم) ؛

}

}

void buildheap (int [] كومة) {

لـ (int i = Heap.Length/2 ؛ i> = 0 ؛ i-) {

Maxheap (كومة ، أنا ، الكومة) ؛

}

}

فرز الفراغ العام (int [] كومة) {

Buildheap (كومة) ؛

لـ (int i = Heap.Length-1 ؛ i> 1 ؛ i-) {

int cache = heap [0] ؛

كومة [0] = كومة [i] ؛

كومة [i] = ذاكرة التخزين المؤقت ؛

maxheap (كومة ، 0 ، i) ؛

}

int cache = heap [0] ؛

كومة [0] = كومة [1] ؛

كومة [1] = ذاكرة التخزين المؤقت ؛

}

الفراغ الثابت العام الرئيسي (سلسلة [] args) {

int [] heap = new int [] {4،1،5،3،7،12،65،7} ؛

Heapsort HS = New Hepsort () ؛

Hs.Sort (كومة) ؛

لـ (int i = 0 ؛ i <heap.length ؛ i ++) {

system.out.println (كومة [i]) ؛

}

}

}