Mga Istraktura ng Data: Pyramid (Binary Heap) sa Java

Hi Hi! Walang sinuman ang tatanggi na ang mga algorithm at istruktura ng data ay ang hindi maikakaila na pundasyon ng programming. Oo, maaari kang magtrabaho bilang isang programmer nang hindi nila nalalaman, ngunit sayang, hindi ka makakarating sa malayo. Samakatuwid, upang palakasin ang iyong base ng kaalaman sa lugar na ito, nais kong pag-usapan ang tungkol sa istruktura ng data bilang isang pyramid (kilala rin bilang heap at binary heap). Bilang isang patakaran, ang mga naturang istruktura ng data ay ginagamit sa iba't ibang mga scheduler at iba pang mga istraktura kung saan kinakailangan upang ipahiwatig ang priyoridad ng iba't ibang mga gawain. Kaya... Ang pyramid ay isang uri ng puno na nagbibigay ng pagpasok/pagtanggal sa oras ng O(logN) at may mga sumusunod na katangian:

• pagkakumpleto. Ang lahat ng mga antas ng puno ay naglalaman ng lahat ng posibleng mga node maliban sa huling isa, na maaari lamang mapunan nang bahagya at napupunan mula kaliwa hanggang kanan;
• Ang isang pyramid ay karaniwang ipinapatupad batay sa isang array;
• Para sa bawat node sa pyramid, mayroong isang pangunahing kondisyon na ang halaga ng bawat node ay mas malaki kaysa sa (o katumbas ng) mga halaga ng mga inapo nito. Alinsunod dito, ang maximum ay maiimbak sa tuktok na elemento.

Isang pyramid na binubuo ng mga vertice na nag-iimbak ng mga halaga na hindi mas mataas kaysa sa 10: Gusto kong tandaan na kumpara sa isang binary search tree, ang isang pyramid ay mahina ang pagkakaayos , dahil sa isang binary search tree ang susi ng kaliwang bata ay mas mababa kaysa sa susi ng tamang bata, at sa isang pyramid ay walang ganoong kondisyon.

Pag-alis ng isang elemento sa pamamagitan ng index

Una, tingnan natin ang pagkakasunud-sunod ng mga aksyon kapag nagtanggal ng napiling node:

1. Tanggalin ang napiling node.
2. Ilipat ang huling node sa huling hilera sa lugar ng tinanggal.
3. Ilipat ito pababa hanggang sa ito ay nasa ibaba ng mas malaki at sa itaas ng mas maliit na node.

Kapag gumagamit ng isang pyramid, kadalasang kinakailangan upang maalis ang tuktok (ang zero na elemento ng panloob na hanay) o ang huling isa (pagkatapos ang mga gumagalaw na operasyon ay maaaring alisin, na iniiwan lamang ang pag-alis ng elemento). Bilang halimbawa ng pagtanggal ng elemento sa pamamagitan ng index sa pyramid na tinitingnan namin sa itaas, tatanggalin namin ang node na may halaga 7:

1. Tinatanggal namin ang napiling node at inilalagay ang huli sa lugar nito, na may halagang 4:

   Ngunit sa posisyong ito, hindi natutugunan ng node na ito ang kundisyon na ang bawat descendant node ay hindi dapat mas malaki kaysa sa pinag-uusapan, tama ba?

   kaya naman:

2. Ipinagpalit namin ito sa pinakamalaki sa mga bata, na may halagang 6:

   Susunod, tinitingnan natin kung mayroong anumang mga inapo na may halaga na mas malaki kaysa sa ating inilipat na elemento, at nakita natin na wala, na nangangahulugan na ang elemento ay pumalit sa lugar nito.

Pagpasok ng bagong elemento

Ano ang mga aksyon kapag naglalagay ng bagong elemento:

1. Ang ipinasok na node ay inilalagay sa dulo ng pyramid.

   Ngunit mayroon tayong kondisyon na ang isang elemento ng bata ay hindi maaaring magkaroon ng isang halaga na mas malaki kaysa sa magulang nito, tama ba?

   kaya naman:

2. Сравниваем новый элемент с родительским элементом. Если новый элемент меньше, то операция закончена, если нет, то он меняется местами с родительским элементом. После — начинает сравниваться с новым родительским элементом, и так далее... До тех пор, пока родительский элемент не будет больше нового.

К примеру, в пирамиду, которая была получена в результате удаления element, мы хотим добавить элемент со meaningм 8:

1. Помещаем новый узел в конец пирамиды:

2. Сравниваем новый элемент с родительским элементом, который имеет meaning 4.

   Так How новый элемент больше родительского, меняем их местами:

3. Сравниваем новый элемент с новым его родителем и видим, что наш элемент больше и его (8>7), поэтому меняем местами и их:

   Опять же, сравниваем элемент с родительский элементом и видим, что в этот раз родительский элемент больше, а это значит что наш новый элемент стал на свое место.

Замена element

При замене element сперва нужно заменить элемент с заданным индексом. Логично, не так ли? Ну а что далее? Ведь новое meaning element уже другое, и не факт, что оно соответствует условию пирамиды. То есть не факт что все дочерние элементы меньше вставляемого element. Также не факт, что родительские элементы больше нового. Поэтому сперва нужно сравнить со старым meaningм element:

• если новый элемент больше, чем он, то нам нужно сравнивать его с родительскими elementми и при надобности менять их местами;
• если же новый элемент меньше, то нужно сравнивать с большим из дочерних элементов и менять местами, если дочерний элемент окажется больше (до тех пор, пока новый элемент не станет на допустимое место).

Давайте же это рассмотрим на нашем примере. Now мы хотим вставить элемент со meaningм 1 instead of element со meaningм 9:

1. Вставляем элемент на место предыдущего:
2. Сравниваем предыдущий элемент 9 и новый 1 и видим, что меньше, а значит, мы будем пробовать смещать вниз.
3. Сравниваем с большим элементом из дочерних, то есть с тем, который имеет meaning 5, и видим, что новый меньше. Поэтому меняем сравниваемые элементы местами:
4. Так How сейчас новых элементов ниже нашего нового уже нет, можно сказать, что элемент встал на свое место.

Реализация пирамиды на Java

После понимания принципа работы данной структуры самое время рассмотреть реализацию пирамиды на Java: Класс, представляющий одну вершину и meaning, которое она содержит:

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

Вывод в консоли:Ну вот, собственно, и всё. Всем спасибо за внимание!