هياكل البيانات: الهرم (الكومة الثنائية) في جافا

مرحبا مرحبا! لن ينكر أحد أن الخوارزميات وهياكل البيانات هي الأساس الذي لا يمكن إنكاره للبرمجة. نعم، يمكنك العمل كمبرمج دون معرفتهم، ولكن للأسف، لن تتمكن من تحقيق الكثير. لذلك، لتعزيز قاعدة معارفك في هذا المجال، أود أن أتحدث عن بنية بيانات تسمى الهرم (المعروف أيضًا باسم الكومة والكومة الثنائية). كقاعدة عامة، يتم استخدام هياكل البيانات هذه في برامج الجدولة المختلفة والهياكل الأخرى التي من الضروري فيها الإشارة إلى أولوية المهام المختلفة. لذا... الهرم هو نوع من الأشجار التي توفر الإدراج/الحذف في وقت O(logN) وله الخصائص التالية:

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

هرم يتكون من رؤوس تخزن قيمًا لا تزيد عن 10: أود أن أشير إلى أنه بالمقارنة مع شجرة البحث الثنائية، فإن الهرم منظم بشكل ضعيف ، لأنه في شجرة البحث الثنائية يكون مفتاح الطفل الأيسر أقل من مفتاح الطفل الصحيح، وفي الهرم لا يوجد مثل هذا الشرط.

إزالة عنصر حسب الفهرس

أولاً، دعونا نلقي نظرة على تسلسل الإجراءات عند حذف العقدة المحددة:

1. حذف العقدة المحددة.
2. انقل العقدة الأخيرة في الصف الأخير إلى مكان العقدة المحذوفة.
3. حركه لأسفل حتى يصبح أسفل العقدة الأكبر وفوق العقدة الأصغر.

عند استخدام الهرم، من الضروري عادةً أن تكون قادرًا على إزالة الجزء العلوي (العنصر الصفري للمصفوفة الداخلية) أو العنصر الأخير (ثم يمكن حذف عمليات النقل، ولم يتبق سوى إزالة العنصر). كمثال على حذف عنصر حسب الفهرس في الهرم الذي ننظر إليه أعلاه، سنقوم بحذف العقدة ذات القيمة 7:

1. نحذف العقدة المحددة ونضع العقدة الأخيرة مكانها والتي تبلغ قيمتها 4:

   لكن في هذا الوضع، لا تستوفي هذه العقدة شرط ألا تكون كل عقدة فرعية أكبر من العقدة المعنية، أليس كذلك؟

   لهذا السبب:

2. ونبادله مع الأكبر من الأطفال والذي قيمته 6:

   بعد ذلك، ننظر لمعرفة ما إذا كان هناك أي فروع لها قيمة أكبر من قيمة العنصر النازح، ونرى أنه لا يوجد أي منها، مما يعني أن العنصر قد أخذ مكانه.

إدخال عنصر جديد

ما هي الإجراءات عند إدراج عنصر جديد:

1. يتم وضع العقدة المدرجة في نهاية الهرم.

   لكن لدينا شرط ألا يكون للعنصر الفرعي قيمة أكبر من قيمة العنصر الأصلي، أليس كذلك؟

   لهذا السبب:

2. قارن العنصر الجديد بالعنصر الأصلي. إذا كان العنصر الجديد أصغر، فستكتمل العملية، وإذا لم يكن كذلك، فسيتم تبديل الأماكن مع العنصر الأصلي. وبعد ذلك تبدأ مقارنته بالعنصر الأصلي الجديد وهكذا... حتى يصبح العنصر الأصلي أكبر من العنصر الجديد.

على سبيل المثال، إلى الهرم الذي تم الحصول عليه عن طريق إزالة عنصر، نريد إضافة عنصر بقيمة 8:

1. ضع عقدة جديدة في نهاية الهرم:

2. قارن العنصر الجديد بالعنصر الأصلي الذي تبلغ قيمته 4.

   وبما أن العنصر الجديد أكبر من العنصر الأصلي، فإننا نستبدلهما:

3. نقارن العنصر الجديد بعنصره الأصلي الجديد ونرى أن العنصر أكبر من العنصر (8>7)، لذلك نقوم بتبديلهما أيضًا:

   مرة أخرى، نقارن العنصر بالعنصر الأصلي ونرى أن العنصر الأصلي أكبر هذه المرة، مما يعني أن العنصر الجديد قد وصل إلى مكانه الصحيح.

استبدال عنصر

عند استبدال عنصر، تحتاج أولاً إلى استبدال العنصر بالفهرس المحدد. منطقي، أليس كذلك؟ ما التالي؟ بعد كل شيء، القيمة الجديدة للعنصر مختلفة بالفعل، وليس حقيقة أنه يتوافق مع شروط الهرم. وهذا يعني أنه ليس حقيقة أن جميع العناصر الفرعية أصغر من العنصر المدرج. كما أنها ليست حقيقة أن العناصر الأصلية أكبر من العناصر الجديدة. لذلك، عليك أولاً المقارنة مع القيمة القديمة للعنصر:

• إذا كان العنصر الجديد أكبر منه، فسنحتاج إلى مقارنته بالعناصر الأصلية، وإذا لزم الأمر، استبدالها؛
• إذا كان العنصر الجديد أصغر، فيجب مقارنته بالعنصر الأكبر من العناصر الفرعية وتبديله إذا كان العنصر الفرعي أكبر (حتى يصل العنصر الجديد إلى مكان مقبول).

دعونا ننظر إلى هذا باستخدام مثالنا. نريد الآن إدراج عنصر بالقيمة 1 بدلاً من عنصر بالقيمة 9:

1. أدخل العنصر بدلاً من العنصر السابق:
2. نقارن العنصر السابق 9 بالعنصر الجديد 1 ونرى أنه أصغر مما يعني أننا سنحاول إزاحته للأسفل.
3. ونقارنه بالعنصر الأكبر من الأطفال، أي بالعنصر الذي قيمته 5، فنرى أن الجديد أصغر. لذلك، نقوم بتبديل العناصر المقارنة:
4. وبما أنه لا يوجد الآن أي عناصر جديدة أسفل العنصر الجديد، فيمكننا القول أن العنصر قد وقع في مكانه.

تنفيذ الهرم في جاوة

بعد فهم كيفية عمل هذه البنية، حان الوقت للنظر في تنفيذ الهرم في Java : فئة تمثل قمة واحدة والقيمة التي تحتوي عليها:

public class Node {
  private int value;

  public Node(int value) {
     this.value = value;
  }

  public int getValue() {
     return this.value;
  }

  public void setValue(int value) {
     this.value = value;
  }
}

الطبقة التي تمثل الهرم نفسه:

public class Heap {
  private Node[] heapArray; // массив со всеми вершинами
  private int maxSize; // размер массива
  private int currentSize; // количество узлов массиве

  public Heap(int maxSize) { // создание пустой пирамиды
     this.maxSize = maxSize;
     this.currentSize = 0;
     heapArray = new Node[maxSize];
  }

  public void printHeap() { // отображение перамиды в консоль
     System.out.println("Массив значений: ");

     for (int n = 0; n < currentSize; n++) {
        if (heapArray[n] != null) {
           System.out.println(heapArray[n].getValue() + " ");
        }
        else {
           System.out.println("-");
        }
     }
     System.out.println();

     int countOfGaps = 32;
     int itemsPerRow = 1;
     int columnNumber = 0; // номер element в данной строке
     String lines = "___________________________________________________________________";
     System.out.println(lines);
     for (int i = 0; i < currentSize; i++) {
        if (columnNumber == 0) {  // проверяем первый элемент ли в текущей строке
           for (int k = 0; k < countOfGaps; k++) { // добавляем предшествующие пробелы
              System.out.print(' ');
           }
        }
        System.out.print(heapArray[i].getValue());// выводим в консоль meaning вершины

        if (++columnNumber == itemsPerRow) { // проверяем последний ли элемент в строке
           countOfGaps /= 2; // уменьшаем количество оступов применяемое для следующей строки
           itemsPerRow *= 2; // указываем, что элементов может быть вдвое больше
           columnNumber = 0; // сбрасываем счётчик для текущего element строки
           System.out.println(); // переходим на нову строку
        }
        else { //переход к следующему элементу
           for (int k = 0; k < countOfGaps * 2 - 2; k++) {
              System.out.print(' '); // добавляем оступы
           }
        }
     }
     System.out.println("\n" + lines); // нижний пункир
  }

  public boolean insertNode(int value) { // вставка нового значения
     if (currentSize == maxSize) { // проверяем не выходим ли мы за рамки массива
        return false;
     }
     Node newNode = new Node(value);// создание вершины с данным meaningм
     heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если meaning вершины позволяет
     return true;
  }

  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index > 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, meaning последнего element
        heapArray[currentSize] = null;// последний элемент удаляем
        displaceDown(index);// проталкиваем вниз новый элемент, чтобы он должное ему место
        return root;
     }
     return null;
  }

  public boolean changeNode(int index, int newValue) {
     if (index < 0 || currentSize<=index) {
        return false;
     }
     int oldValue = heapArray[index].getValue(); // сохраняем старое meaning
     heapArray[index].setValue(newValue); // присваиваем новое

     if (oldValue < newValue) {// если узел повышается
        displaceUp(index);     // выполняется смещение вверх
     }
     else {                  // если понижается
        displaceDown(index);   // смещение вниз
     }
     return true;
  }

  private void displaceUp(int index) { //смещение вверх
     int parentIndex = (index - 1) / 2; // узнаем индекс родителя
     Node bottom = heapArray[index]; // берем элемент
     while (index > 0 && heapArray[parentIndex].getValue() < bottom.getValue()) {// если родительский элемент меньше
        heapArray[index] = heapArray[parentIndex];// то меняем его местами с рассматриваемым
        index = parentIndex;
        parentIndex = (parentIndex - 1) / 2;// берем новый родительский индекс и повторяем сравнение элементов
     }
     heapArray[index] = bottom;// соохраняем результат
  }

  private void displaceDown(int index) {// смещение вниз
     int largerChild;
     Node top = heapArray[index]; // сохранение корня, пока у узла есть хотя бы один потомок
     while (index < currentSize / 2) {// если данное condition не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого

        if (rightChild < currentSize && heapArray[leftChild].getValue() < heapArray[rightChild].getValue()) {
           largerChild = rightChild;
        }// вычисляем ребенка вершину с наибольшим числовым meaningм
        else {
           largerChild = leftChild;
        }

        if (top.getValue() >= heapArray[largerChild].getValue()) {// если meaning вершины больше or равно
           //значени его наибольшего ребенка
           break;// то выходим из метода
        }

        heapArray[index] = heapArray[largerChild];// заменяем вершину, большей дочерней вершиной
        index = largerChild; // текущий индекс переходит вниз
     }
     heapArray[index] = top; // задаем конечное местоположение для element
  }
}

أخيرًا، دعونا نلقي نظرة على هرمنا أثناء العمل:

public class Solution {

  public static void main(String[] args) {
     // задаем начальные данные:
     Heap heap = new Heap(31);
     heap.insertNode(120);
     heap.insertNode(40);
     heap.insertNode(50);
     heap.insertNode(80);
     heap.insertNode(20);
     heap.insertNode(100);
     heap.insertNode(150);
     heap.insertNode(30);
     heap.insertNode(210);
     heap.insertNode(180);
     heap.insertNode(10);
     heap.insertNode(90);
      // выводим начальную пирамиду в консоль
     heap.printHeap();

إخراج وحدة التحكم:

// изменяем элемент под индексом 0 с 210 на 15, и выводим в консоль измененную пирамиду
     heap.changeNode(0,15);
     heap.printHeap();

إخراج وحدة التحكم:

// удаляем элемент под индексом 3, который имеет meaning 80 и смотрим на изменившуюся пирамиду
     heap.removeNode(3);
     heap.printHeap();
  }
}

إخراج وحدة التحكم: حسنًا، هذا كل شيء. شكرا لكم جميعا على اهتمامكم!