Struktur Data: Piramid (Timbunan Binari) di Jawa

Hi hi! Tiada siapa yang akan menafikan bahawa algoritma dan struktur data adalah asas pengaturcaraan yang tidak dapat dinafikan. Ya, anda boleh bekerja sebagai pengaturcara tanpa pengetahuan mereka, tetapi sayangnya, anda tidak akan pergi jauh. Oleh itu, untuk mengukuhkan pangkalan pengetahuan anda dalam bidang ini, saya ingin bercakap tentang struktur data seperti piramid (juga dikenali sebagai timbunan dan timbunan binari). Sebagai peraturan, struktur data tersebut digunakan dalam pelbagai penjadual dan struktur lain di mana ia perlu untuk menunjukkan keutamaan pelbagai tugas. Jadi... Piramid ialah sejenis pokok yang menyediakan sisipan/pemadaman dalam masa O(logN) dan mempunyai sifat berikut:

• kesempurnaan. Semua peringkat pokok mengandungi semua kemungkinan nod kecuali yang terakhir, yang hanya boleh diisi sebahagian dan yang diisi dari kiri ke kanan;
• Piramid biasanya dilaksanakan berdasarkan tatasusunan;
• Bagi setiap nod dalam piramid, terdapat syarat asas bahawa nilai setiap nod adalah lebih besar daripada (atau sama dengan) nilai keturunannya. Sehubungan itu, maksimum akan disimpan dalam elemen teratas.

Piramid yang terdiri daripada bucu yang menyimpan nilai tidak lebih tinggi daripada 10: Saya ingin ambil perhatian bahawa berbanding dengan pokok carian binari, piramid tersusun dengan lemah , kerana dalam pokok carian binari kunci anak kiri adalah kurang daripada kunci anak yang betul, dan dalam piramid tidak ada keadaan sedemikian.

Mengalih keluar elemen mengikut indeks

Mula-mula, mari kita lihat urutan tindakan apabila memadamkan nod yang dipilih:

1. Padamkan nod yang dipilih.
2. Alihkan nod terakhir dalam baris terakhir ke tempat nod yang dipadamkan.
3. Gerakkannya ke bawah sehingga ia berada di bawah nod yang lebih besar dan di atas nod yang lebih kecil.

Apabila menggunakan piramid, ia biasanya perlu untuk dapat mengalih keluar bahagian atas (elemen sifar tatasusunan dalaman) atau yang terakhir (kemudian operasi bergerak boleh ditinggalkan, hanya meninggalkan penyingkiran elemen). Sebagai contoh memadamkan elemen mengikut indeks dalam piramid yang kita lihat di atas, kita akan memadamkan nod dengan nilai 7:

1. Kami memadamkan nod yang dipilih dan meletakkan yang terakhir di tempatnya, yang mempunyai nilai 4:

   Tetapi dalam kedudukan ini, nod ini tidak memenuhi syarat bahawa setiap nod keturunan tidak boleh lebih besar daripada yang dimaksudkan, bukan?

   Itulah sebabnya:

2. Kami menukarnya dengan yang terbesar daripada kanak-kanak, yang mempunyai nilai 6:

   Seterusnya, kami melihat untuk melihat sama ada terdapat mana-mana keturunan dengan nilai yang lebih besar daripada unsur anjakan kami, dan kami melihat bahawa tidak ada, yang bermaksud unsur itu telah mengambil tempatnya.

Memasukkan elemen baharu

Apakah tindakan apabila memasukkan elemen baharu:

1. Nod yang dimasukkan diletakkan di hujung piramid.

   Tetapi kita mempunyai syarat bahawa elemen kanak-kanak tidak boleh mempunyai nilai yang lebih besar daripada induknya, bukan?

   Itulah sebabnya:

2. Bandingkan elemen baharu dengan elemen induk. Jika elemen baharu lebih kecil, maka operasi selesai; jika tidak, ia menukar tempat dengan elemen induk. Selepas itu, ia mula dibandingkan dengan elemen induk baru, dan seterusnya... Sehingga elemen induk lebih besar daripada yang baru.

Sebagai contoh, kepada piramid yang diperoleh dengan mengalih keluar elemen, kami ingin menambah elemen dengan nilai 8:

1. Letakkan nod baharu di hujung piramid:

2. Bandingkan elemen baharu dengan elemen induk, yang mempunyai nilai 4.

   Memandangkan elemen baharu lebih besar daripada induk, kami menukarnya:

3. Kami membandingkan elemen baharu dengan induk baharunya dan melihat bahawa elemen kami lebih besar daripada elemen (8>7), jadi kami menukarnya juga:

   Sekali lagi, kami membandingkan elemen dengan elemen induk dan melihat bahawa kali ini elemen induk adalah lebih besar, yang bermaksud bahawa elemen baru kami telah jatuh ke tempatnya.

Menggantikan elemen

Apabila menggantikan elemen, anda perlu menggantikan elemen dengan indeks yang diberikan terlebih dahulu. Logik kan? Jadi apa seterusnya? Lagipun, nilai baru unsur itu sudah berbeza, dan bukan fakta bahawa ia sepadan dengan keadaan piramid. Iaitu, bukan fakta bahawa semua elemen kanak-kanak adalah lebih kecil daripada elemen yang dimasukkan. Ia juga bukan fakta bahawa elemen induk lebih besar daripada yang baru. Oleh itu, anda perlu membandingkan dahulu dengan nilai lama elemen:

• jika elemen baharu lebih besar daripadanya, maka kita perlu membandingkannya dengan elemen induk dan, jika perlu, menukarnya;
• jika elemen baru lebih kecil, maka ia mesti dibandingkan dengan elemen kanak-kanak yang lebih besar dan ditukar jika elemen kanak-kanak lebih besar (sehingga elemen baru berada di tempat yang sah).

Mari lihat ini menggunakan contoh kami. Sekarang kita ingin memasukkan elemen dengan nilai 1 dan bukannya elemen dengan nilai 9:

1. Masukkan elemen sebagai ganti yang sebelumnya:
2. Kami membandingkan elemen sebelumnya 9 dan yang baharu 1 dan melihat bahawa ia lebih kecil, yang bermaksud kami akan cuba mengalihkannya ke bawah.
3. Kami membandingkannya dengan elemen terbesar dari kanak-kanak, iaitu, dengan yang mempunyai nilai 5, dan kami melihat bahawa yang baru lebih kecil. Oleh itu, kami menukar elemen yang dibandingkan:
4. Memandangkan kini tiada elemen baharu di bawah elemen baharu kami, kita boleh mengatakan bahawa elemen itu telah jatuh ke tempatnya.

Pelaksanaan piramid di Jawa

Selepas memahami cara struktur ini berfungsi, tiba masanya untuk melihat pelaksanaan piramid dalam Java : Kelas yang mewakili satu bucu dan nilai yang terkandung di dalamnya:

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

Akhir sekali, mari kita lihat piramid kita dalam tindakan:

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: Baiklah, itu sahaja. Terima kasih semua atas perhatian anda!