Struktur Data: Piramida (Binary Heap) di Java

Hai Hai! Tidak ada yang akan menyangkal bahwa algoritma dan struktur data adalah dasar pemrograman yang tidak dapat disangkal. Ya, Anda bisa bekerja sebagai programmer tanpa sepengetahuan mereka, tapi sayangnya, Anda tidak akan berhasil. Oleh karena itu, untuk memperkuat basis pengetahuan Anda di bidang ini, saya ingin berbicara tentang struktur data seperti piramida (juga dikenal sebagai heap dan biner heap). Biasanya, struktur data seperti itu digunakan di berbagai penjadwal dan struktur lain yang memerlukan penentuan prioritas berbagai tugas. Jadi... Piramida adalah jenis pohon yang menyediakan penyisipan/penghapusan dalam waktu O(logN) dan memiliki properti berikut:

• Kelengkapan. Semua level pohon berisi semua node yang mungkin kecuali yang terakhir, yang hanya dapat diisi sebagian dan diisi dari kiri ke kanan;
• Piramida biasanya diimplementasikan berdasarkan array;
• Untuk setiap simpul dalam piramida, terdapat syarat mendasar yaitu nilai setiap simpul lebih besar dari (atau sama dengan) nilai turunannya. Oleh karena itu, maksimum akan disimpan di elemen teratas.

Piramida yang terdiri dari simpul-simpul yang menyimpan nilai tidak lebih tinggi dari 10: Saya ingin mencatat bahwa dibandingkan dengan pohon pencarian biner, piramida memiliki urutan yang lemah , karena dalam pohon pencarian biner, kunci anak kiri lebih kecil dari kunci anak yang tepat, dan dalam piramida tidak ada kondisi seperti itu.

Menghapus elemen berdasarkan indeks

Pertama, mari kita lihat urutan tindakan saat menghapus node yang dipilih:

1. Hapus node yang dipilih.
2. Pindahkan node terakhir pada baris terakhir ke tempat node yang dihapus.
3. Pindahkan ke bawah hingga berada di bawah node yang lebih besar dan di atas node yang lebih kecil.

Saat menggunakan piramida, biasanya diperlukan untuk menghilangkan bagian atas (elemen nol dari array internal) atau yang terakhir (kemudian operasi pemindahan dapat dihilangkan, hanya menyisakan penghapusan elemen). Sebagai contoh penghapusan elemen berdasarkan indeks pada piramida yang kita lihat di atas, kita akan menghapus node dengan nilai 7:

1. Kami menghapus node yang dipilih dan menempatkan node terakhir di tempatnya, yang memiliki nilai 4:

   Namun pada posisi ini, node ini tidak memenuhi syarat bahwa setiap node turunannya tidak boleh lebih besar dari node yang dimaksud bukan?

   Itu sebabnya:

2. Kita tukar dengan anak terbesar yang bernilai 6:

   Selanjutnya, kita melihat apakah ada keturunan yang nilainya lebih besar dari elemen yang dipindahkan, dan kita melihat bahwa tidak ada satu pun, yang berarti elemen tersebut telah menggantikan tempatnya.

Memasukkan elemen baru

Tindakan apa yang dilakukan saat menyisipkan elemen baru:

1. Node yang disisipkan ditempatkan di ujung piramida.

   Tapi kita punya syarat bahwa elemen anak tidak boleh memiliki nilai lebih besar dari induknya, bukan?

   Itu sebabnya:

2. Bandingkan elemen baru dengan elemen induk. Jika elemen baru lebih kecil, maka operasi selesai; jika tidak, maka bertukar tempat dengan elemen induk. Setelah itu mulai dibandingkan dengan elemen induk yang baru, dan seterusnya... Hingga elemen induk lebih besar dari yang baru.

Misalnya, pada piramida yang diperoleh dengan menghilangkan sebuah elemen, kita ingin menambahkan elemen dengan nilai 8:

1. Tempatkan simpul baru di ujung piramida:

2. Bandingkan elemen baru dengan elemen induk yang bernilai 4.

   Karena elemen baru lebih besar dari elemen induknya, kami menukarnya:

3. Kita membandingkan elemen baru dengan induk barunya dan melihat bahwa elemen kita lebih besar darinya (8>7), jadi kita menukarnya juga:

   Sekali lagi, kita membandingkan elemen dengan elemen induk dan melihat bahwa kali ini elemen induk lebih besar, yang berarti elemen baru kita sudah sesuai.

Mengganti elemen

Saat mengganti suatu elemen, Anda harus mengganti elemen tersebut terlebih dahulu dengan indeks yang diberikan. Logis, bukan? Jadi apa selanjutnya? Lagi pula, nilai baru suatu elemen sudah berbeda, dan bukan fakta bahwa itu sesuai dengan kondisi piramida. Artinya, bukan fakta bahwa semua elemen turunan lebih kecil dari elemen yang disisipkan. Juga bukan fakta bahwa elemen induk lebih besar dari elemen baru. Oleh karena itu, pertama-tama Anda perlu membandingkan dengan nilai elemen yang lama:

• jika elemen baru lebih besar darinya, maka kita perlu membandingkannya dengan elemen induk dan, jika perlu, menukarnya;
• jika elemen baru lebih kecil, maka harus dibandingkan dengan elemen turunan yang lebih besar dan ditukar jika elemen turunan lebih besar (sampai elemen baru berada di tempat yang valid).

Mari kita lihat ini menggunakan contoh kita. Sekarang kita ingin menyisipkan elemen dengan nilai 1, bukan elemen dengan nilai 9:

1. Sisipkan elemen di tempat yang sebelumnya:
2. Kita bandingkan elemen sebelumnya 9 dan elemen baru 1 dan lihat bahwa elemen tersebut lebih kecil, yang berarti kita akan mencoba menggesernya ke bawah.
3. Kita bandingkan dengan elemen terbesar dari anak, yaitu dengan elemen yang bernilai 5, dan kita melihat elemen baru lebih kecil. Oleh karena itu, kami menukar elemen yang dibandingkan:
4. Karena sekarang tidak ada elemen baru di bawah elemen baru kita, kita dapat mengatakan bahwa elemen tersebut telah jatuh pada tempatnya.

Implementasi piramida di Jawa

Setelah memahami cara kerja struktur ini, sekarang saatnya melihat implementasi piramida di Java : Sebuah kelas yang mewakili satu titik dan nilai yang dikandungnya:

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 yang mewakili piramida itu sendiri:

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

Terakhir, mari kita lihat cara kerja piramida kita:

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

Keluaran konsol:

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

Keluaran konsol:

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

Keluaran konsol: Ya, itu saja. Terima kasih atas perhatian Anda!