Struktury danych: piramida (sterta binarna) w Javie

Cześć cześć! Nikt nie zaprzeczy, że algorytmy i struktury danych są niezaprzeczalnym fundamentem programowania. Tak, możesz pracować jako programista bez ich wiedzy, ale niestety daleko nie zajdziesz. Dlatego, aby wzmocnić Twoją wiedzę w tym zakresie, chciałbym poruszyć temat takiej struktury danych jak piramida (znana również jako sterta i sterta binarna). Z reguły takie struktury danych są wykorzystywane w różnych planistach i innych strukturach, w których konieczne jest wskazanie priorytetu różnych zadań. Zatem... Piramida jest rodzajem drzewa, które umożliwia wstawianie/usuwanie w czasie O(logN) i ma następujące właściwości:

• Kompletność. Wszystkie poziomy drzewa zawierają wszystkie możliwe węzły z wyjątkiem ostatniego, który może być wypełniony tylko częściowo i który jest wypełniany od lewej do prawej;
• Piramida jest zwykle implementowana w oparciu o tablicę;
• Dla każdego węzła piramidy istnieje podstawowy warunek, że wartość każdego węzła jest większa (lub równa) wartości jego potomków. W związku z tym maksimum zostanie zapisane w górnym elemencie.

Piramida składająca się z wierzchołków przechowujących wartości nie większe niż 10: Chciałbym zauważyć, że w porównaniu do drzewa wyszukiwania binarnego piramida jest słabo uporządkowana , ponieważ w drzewie wyszukiwania binarnego klucz lewego dziecka jest mniejszy niż klucz właściwego dziecka, a w piramidzie nie ma takiego warunku.

Usuwanie elementu według indeksu

Na początek przyjrzyjmy się kolejności działań przy usuwaniu wybranego węzła:

1. Usuń wybrany węzeł.
2. Przesuń ostatni węzeł w ostatnim wierszu na miejsce usuniętego.
3. Przesuń go w dół, aż znajdzie się poniżej większego i powyżej mniejszego węzła.

W przypadku piramidy zazwyczaj konieczna jest możliwość usunięcia wierzchołka (element zerowy tablicy wewnętrznej) lub ostatniego (wówczas można pominąć operacje przesuwania, pozostawiając jedynie usunięcie elementu). Jako przykład usunięcia elementu według indeksu w piramidzie, o której mowa powyżej, usuniemy węzeł o wartości 7:

1. Usuwamy wybrany węzeł i umieszczamy na jego miejscu ostatni, który ma wartość 4:

   Ale w tej pozycji węzeł ten nie spełnia warunku, że każdy węzeł potomny nie powinien być większy od rozpatrywanego, prawda?

   Dlatego:

2. Zamieniamy go z największym z dzieci, które ma wartość 6:

   Następnie sprawdzamy, czy są jacyś potomkowie o wartości większej niż wartość naszego przesuniętego elementu i widzimy, że ich nie ma, co oznacza, że ​​element zajął swoje miejsce.

Wstawienie nowego elementu

Jakie są działania podczas wstawiania nowego elementu:

1. Wstawiony węzeł umieszczany jest na końcu ostrosłupa.

   Ale mamy warunek, że element podrzędny nie może mieć wartości większej niż jego element nadrzędny, prawda?

   Dlatego:

2. Porównaj nowy element z elementem nadrzędnym. Jeśli nowy element jest mniejszy, operacja zostaje zakończona, jeśli nie, następuje zamiana miejscami z elementem nadrzędnym. Następnie zaczyna się porównywanie go z nowym elementem nadrzędnym i tak dalej... Aż do momentu, gdy element nadrzędny jest większy od nowego.

Przykładowo do piramidy powstałej poprzez usunięcie elementu chcemy dodać element o wartości 8:

1. Umieść nowy węzeł na końcu piramidy:

2. Porównaj nowy element z elementem nadrzędnym, który ma wartość 4.

   Ponieważ nowy element jest większy od rodzica, zamieniamy je:

3. Porównujemy nowy element z jego nowym rodzicem i widzimy, że nasz element jest większy niż jego (8>7), więc je też zamieniamy:

   Ponownie porównujemy element z elementem nadrzędnym i widzimy, że tym razem element nadrzędny jest większy, co oznacza, że ​​nasz nowy element wpasował się na swoje miejsce.

Wymiana elementu

Zastępując element, należy najpierw zastąpić element o podanym indeksie. Logiczne, prawda? Więc, co dalej? Przecież nowa wartość elementu jest już inna i nie jest faktem, że odpowiada warunkom piramidy. Oznacza to, że nie jest faktem, że wszystkie elementy podrzędne są mniejsze niż element wstawiony. Nie jest też faktem, że elementy macierzyste są większe od nowego. Dlatego najpierw musisz porównać ze starą wartością elementu:

• jeśli nowy element jest od niego większy, to musimy go porównać z elementami nadrzędnymi i w razie potrzeby zamienić je miejscami;
• jeśli nowy element jest mniejszy, należy go porównać z większym z elementów potomnych i zamienić, jeśli element potomny jest większy (dopóki nowy element nie znajdzie się w prawidłowym miejscu).

Spójrzmy na to na naszym przykładzie. Teraz chcemy wstawić element o wartości 1 zamiast elementu o wartości 9:

1. Wstaw element w miejsce poprzedniego:
2. Porównujemy poprzedni element 9 z nowym 1 i widzimy, że jest mniejszy, co oznacza, że ​​spróbujemy go przesunąć w dół.
3. Porównujemy go z największym elementem od dzieci, czyli z tym, który ma wartość 5 i widzimy, że nowy jest mniejszy. Dlatego zamieniamy porównywane elementy:
4. Skoro pod naszym nowym nie ma już nowych elementów, to można powiedzieć, że element wskoczył na swoje miejsce.

Implementacja piramidy w Javie

Po zrozumieniu, jak działa ta struktura, czas przyjrzeć się implementacji piramidy w Javie : Klasa reprezentująca jeden wierzchołek i wartość, którą zawiera:

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

Klasa reprezentująca samą piramidę:

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

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

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

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

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

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

Na koniec przyjrzyjmy się naszej piramidzie w działaniu:

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

Wyjście konsoli:

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

Wyjście konsoli:

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

Dane wyjściowe konsoli: Cóż, to wszystko. Dziękuję wszystkim za uwagę!