Datenstrukturen: Pyramide (Binärer Heap) in Java

Hallo Hallo! Niemand wird leugnen, dass Algorithmen und Datenstrukturen die unbestreitbare Grundlage der Programmierung sind. Ja, Sie können als Programmierer arbeiten, ohne sie zu kennen, aber leider kommen Sie damit nicht weit. Um Ihre Wissensbasis in diesem Bereich zu stärken, möchte ich daher über eine Datenstruktur namens Pyramide (auch bekannt als Heap und binärer Heap) sprechen. In der Regel werden solche Datenstrukturen in verschiedenen Schedulern und anderen Strukturen verwendet, in denen die Priorität verschiedener Aufgaben angegeben werden muss. Also... Eine Pyramide ist eine Art Baum, der das Einfügen/Löschen in O(logN) -Zeit ermöglicht und die folgenden Eigenschaften hat:

• Vollständigkeit. Alle Ebenen des Baums enthalten alle möglichen Knoten bis auf den letzten, der nur teilweise gefüllt werden kann und von links nach rechts gefüllt wird;
• Eine Pyramide wird normalerweise basierend auf einem Array implementiert.
• Für jeden Knoten in der Pyramide gibt es eine grundlegende Bedingung, dass der Wert jedes Knotens größer (oder gleich) den Werten seiner Nachkommen ist. Dementsprechend wird das Maximum im obersten Element gespeichert.

Eine Pyramide, die aus Eckpunkten besteht, die Werte von nicht mehr als 10 speichern: Ich möchte darauf hinweisen, dass eine Pyramide im Vergleich zu einem binären Suchbaum schwach geordnet ist , da in einem binären Suchbaum der Schlüssel des linken Kindes kleiner ist als der Schlüssel des richtigen Kindes, und in einer Pyramide gibt es keine solche Bedingung.

Entfernen eines Elements nach Index

Schauen wir uns zunächst die Abfolge der Aktionen beim Löschen eines ausgewählten Knotens an:

1. Löschen Sie den ausgewählten Knoten.
2. Verschieben Sie den letzten Knoten in der letzten Zeile an die Stelle des gelöschten Knotens.
3. Bewegen Sie ihn nach unten, bis er sich unter dem größeren und über dem kleineren Knoten befindet.

Bei der Verwendung einer Pyramide ist es normalerweise erforderlich, die Spitze (das Nullelement des internen Arrays) oder das letzte Element entfernen zu können (dann können die Verschiebungsvorgänge weggelassen werden, sodass nur noch das Element entfernt werden muss). Als Beispiel für das Löschen eines Elements nach Index in der oben betrachteten Pyramide löschen wir den Knoten mit dem Wert 7:

1. Wir löschen den ausgewählten Knoten und platzieren an seiner Stelle den letzten, der den Wert 4 hat:

   Aber in dieser Position erfüllt dieser Knoten nicht die Bedingung, dass jeder Nachkommenknoten nicht größer sein darf als der betreffende, oder?

   Deshalb:

2. Wir tauschen es mit dem größten der Kinder aus, das einen Wert von 6 hat:

   Als nächstes schauen wir, ob es Nachkommen gibt, deren Wert größer als der unseres verdrängten Elements ist, und stellen fest, dass es keine gibt, was bedeutet, dass das Element seinen Platz eingenommen hat.

Einfügen eines neuen Elements

Was sind die Aktionen beim Einfügen eines neuen Elements:

1. Der eingefügte Knoten wird am Ende der Pyramide platziert.

   Aber wir haben die Bedingung, dass ein untergeordnetes Element keinen größeren Wert als sein übergeordnetes Element haben kann, oder?

   Deshalb:

2. Vergleichen Sie das neue Element mit dem übergeordneten Element. Wenn das neue Element kleiner ist, ist die Operation abgeschlossen. Wenn nicht, tauscht es die Plätze mit dem übergeordneten Element. Danach beginnt der Vergleich mit dem neuen übergeordneten Element usw., bis das übergeordnete Element größer als das neue ist.

Beispielsweise möchten wir zu der Pyramide, die durch Entfernen eines Elements entstanden ist, ein Element mit dem Wert 8 hinzufügen:

1. Platzieren Sie einen neuen Knoten am Ende der Pyramide:

2. Vergleichen Sie das neue Element mit dem übergeordneten Element, das den Wert 4 hat.

   Da das neue Element größer als das übergeordnete Element ist, tauschen wir sie aus:

3. Wir vergleichen das neue Element mit seinem neuen übergeordneten Element und stellen fest, dass unser Element größer als sein (8>7) ist, also tauschen wir sie auch aus:

   Wieder vergleichen wir das Element mit dem übergeordneten Element und stellen fest, dass dieses Mal das übergeordnete Element größer ist, was bedeutet, dass unser neues Element an seinen Platz passt.

Ersetzen eines Elements

Wenn Sie ein Element ersetzen, müssen Sie zunächst das Element durch den angegebenen Index ersetzen. Logisch, oder? Was kommt also als Nächstes? Schließlich ist der neue Wert des Elements bereits ein anderer, und es ist keine Tatsache, dass er den Bedingungen der Pyramide entspricht. Das heißt, es ist keine Tatsache, dass alle untergeordneten Elemente kleiner als das eingefügte Element sind. Es ist auch keine Tatsache, dass die übergeordneten Elemente größer sind als die neuen. Daher müssen Sie zunächst mit dem alten Wert des Elements vergleichen:

• Wenn das neue Element größer ist als es, müssen wir es mit den übergeordneten Elementen vergleichen und sie gegebenenfalls austauschen.
• Wenn das neue Element kleiner ist, muss es mit dem größeren der untergeordneten Elemente verglichen und ausgetauscht werden, wenn das untergeordnete Element größer ist (bis das neue Element an einer gültigen Stelle ist).

Schauen wir uns das anhand unseres Beispiels an. Nun wollen wir statt eines Elements mit dem Wert 9 ein Element mit dem Wert 1 einfügen:

1. Fügen Sie das Element anstelle des vorherigen ein:
2. Wir vergleichen das vorherige Element 9 und das neue 1 und stellen fest, dass es kleiner ist, was bedeutet, dass wir versuchen werden, es nach unten zu verschieben.
3. Wir vergleichen es mit dem größten Element der Kinder, also mit dem, das den Wert 5 hat, und sehen, dass das neue kleiner ist. Deshalb tauschen wir die verglichenen Elemente aus:
4. Da es jetzt keine neuen Elemente unter unserem neuen gibt, können wir sagen, dass das Element seinen Platz gefunden hat.

Implementierung einer Pyramide in Java

Nachdem Sie verstanden haben, wie diese Struktur funktioniert, ist es an der Zeit, sich die Implementierung einer Pyramide in Java anzusehen : Eine Klasse, die einen Scheitelpunkt und den darin enthaltenen Wert darstellt:

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;
  }
}

Die Klasse, die die Pyramide selbst darstellt:

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());// выводим в консоль Bedeutung вершины

        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);// создание вершины с данным Bedeutungм
     heapArray[currentSize] = newNode;// вершину задём в самый низ дерева
     displaceUp(currentSize++);// пытаемся поднять вершину, если Bedeutung вершины позволяет
     return true;
  }

  public Node removeNode(int index) { // удалить элемент по индексу массива
     if(index > 0 && currentSize > index) {
        Node root = heapArray[index];
        heapArray[index] = heapArray[--currentSize]; // задаём элементу с переданным индексом, Bedeutung последнего 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(); // сохраняем старое Bedeutung
     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) {// если данное Zustand не выполняется то элемент уже в самом низу пирамиды
        int leftChild = 2 * index + 1; // вычисляем индексы в массиве для левого узла ребенка
        int rightChild = leftChild + 1;// и правого

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

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

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

Schauen wir uns zum Schluss unsere Pyramide in Aktion an:

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();

Konsolenausgabe:

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

Konsolenausgabe:

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

Konsolenausgabe: Nun, das ist alles. Vielen Dank für Ihre Aufmerksamkeit!