Struktur Data: Piramida (Binary Heap) ing Jawa

Hi Hi! Ora ana sing bakal nolak yen algoritma lan struktur data minangka pondasi pemrograman sing ora bisa dipungkiri. Ya, sampeyan bisa dadi programmer tanpa ngerti, nanging sayangé, sampeyan ora bakal adoh. Mula, kanggo nguatake basis kawruh sampeyan ing wilayah iki, aku arep ngomong babagan struktur data sing diarani piramida (uga dikenal minangka tumpukan lan tumpukan biner). Minangka aturan, struktur data kasebut digunakake ing macem-macem penjadwal lan struktur liyane sing kudu nuduhake prioritas macem-macem tugas. Dadi ... Piramida minangka jinis wit sing nyedhiyakake sisipan / pambusakan ing wektu O(logN) lan nduweni sifat ing ngisor iki:

• Kelengkapan. Kabeh tingkat wit ngemot kabeh simpul sing bisa ditindakake kajaba sing pungkasan, sing mung bisa diisi sebagian lan diisi saka kiwa menyang tengen;
• Piramida biasane dileksanakake adhedhasar array;
• Kanggo saben simpul ing piramida, ana syarat dhasar yen nilai saben simpul luwih gedhe tinimbang (utawa padha karo) nilai turunane. Patut, maksimum bakal disimpen ing unsur ndhuwur.

Piramida sing kasusun saka vertices sing nyimpen nilai ora luwih saka 10: Aku pengin dicathet yen dibandhingake karo wit telusuran binar, piramida diurutake kanthi lemah , amarga ing wit telusuran binar kunci anak kiwa kurang saka tombol anak tengen, lan ing piramida ora ana kondisi kuwi.

Mbusak unsur kanthi indeks

Pisanan, ayo ndeleng urutan tumindak nalika mbusak simpul sing dipilih:

1. Mbusak simpul sing dipilih.
2. Pindhah simpul pungkasan ing baris pungkasan menyang panggonan sing wis dibusak.
3. Pindhah mudhun nganti ngisor simpul sing luwih gedhe lan ndhuwur simpul cilik.

Nalika nggunakake piramida, biasane kudu bisa mbusak ndhuwur (unsur nul saka array internal) utawa sing pungkasan (banjur operasi obah bisa diilangi, mung ninggalake unsur kasebut). Minangka conto mbusak unsur kanthi indeks ing piramida sing kita deleng ing ndhuwur, kita bakal mbusak simpul kanthi nilai 7:

1. Kita mbusak simpul sing dipilih lan nyelehake ing panggonan sing pungkasan, sing nduweni nilai 4:

   Nanging ing posisi iki, simpul iki ora nyukupi syarat saben simpul keturunan ora luwih gedhe tinimbang sing dimaksud, ta?

   Mulane:

2. Kita ngganti karo sing paling gedhe saka bocah-bocah, sing nduweni nilai 6:

   Sabanjure, kita katon kanggo ndeleng apa ana turunan karo nilai luwih saka unsur terlantar kita, lan kita weruh sing ora ana, kang tegese unsur wis njupuk Panggonan.

Nglebokake unsur anyar

Apa tumindak nalika nglebokake unsur anyar:

1. Simpul sing dipasang dilebokake ing mburi piramida.

   Nanging kita duwe syarat yen unsur anak ora bisa duwe nilai sing luwih gedhe tinimbang wong tuwa, ta?

   Mulane:

2. Bandingake unsur anyar karo unsur induk. Yen unsur anyar luwih cilik, banjur operasi rampung; yen ora, banjur ngganti panggonan karo unsur induk. Sawise iku, wiwit dibandhingake karo unsur induk anyar, lan liya-liyane ... Nganti unsur induk luwih gedhe tinimbang sing anyar.

Contone, menyang piramida sing dipikolehi kanthi ngilangi unsur, kita pengin nambah unsur kanthi nilai 8:

1. Selehake simpul anyar ing mburi piramida:

2. Bandhingake unsur anyar karo unsur induk, sing nduweni nilai 4.

   Amarga unsur anyar luwih gedhe tinimbang wong tuwa, kita ganti:

3. Kita mbandhingake unsur anyar karo induk anyar lan ndeleng manawa unsur luwih gedhe tinimbang (8> 7), mula kita uga ngganti:

   Maneh, kita mbandhingake unsur karo unsur induk lan ndeleng yen wektu iki unsur induk luwih gedhe, tegese unsur anyar kita wis tiba.

Ngganti unsur

Nalika ngganti unsur, sampeyan kudu ngganti unsur karo indeks diwenehi. Logis, kan? Dadi apa sabanjure? Sawise kabeh, nilai anyar saka unsur wis beda, lan iku ora kasunyatan sing cocog karo kondisi piramida. Tegese, ora kasunyatan manawa kabeh unsur bocah luwih cilik tinimbang unsur sing dilebokake. Uga ora kasunyatan manawa unsur induk luwih gedhe tinimbang sing anyar. Mula, sampeyan kudu mbandhingake karo nilai lawas saka unsur kasebut:

• yen unsur anyar luwih gedhe tinimbang, mula kita kudu mbandhingake karo unsur induk lan, yen perlu, ngganti;
• yen unsur anyar luwih cilik, mula kudu dibandhingake karo unsur anak sing luwih gedhe lan diganti yen unsur anak luwih gedhe (nganti unsur anyar ana ing panggonan sing bener).

Ayo ndeleng iki nggunakake conto kita. Saiki kita pengin nglebokake unsur kanthi nilai 1 tinimbang unsur kanthi nilai 9:

1. Lebokake unsur ing panggonan sing sadurunge:
2. Kita mbandhingake unsur sadurunge 9 lan sing anyar 1 lan ndeleng manawa luwih cilik, tegese kita bakal nyoba nggeser mudhun.
3. Kita mbandhingake karo unsur paling gedhe saka bocah-bocah, yaiku, sing nduweni nilai 5, lan kita weruh yen sing anyar luwih cilik. Dadi, kita ngganti unsur sing dibandhingake:
4. Wiwit saiki ora ana unsur anyar ing sangisore sing anyar, kita bisa ngomong yen unsur kasebut wis tiba.

Implementasi piramida ing Jawa

Sawise ngerti cara kerjane struktur iki, wektune kanggo ndeleng implementasi piramida ing Jawa : Kelas sing makili siji vertex lan nilai sing ana:

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

Kelas sing makili piramida dhewe:

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

Pungkasan, ayo goleki piramida sing ditindakake:

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

Output konsol:

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

Output konsol:

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

Output konsol: Inggih, iku kabeh. Matur nuwun kabeh kanggo manungsa waé!