Cấu trúc dữ liệu: Kim tự tháp (Heap nhị phân) trong Java

Xin chào Xin chào! Không ai có thể phủ nhận rằng thuật toán và cấu trúc dữ liệu là nền tảng không thể phủ nhận của lập trình. Đúng, bạn có thể làm lập trình viên mà không cần biết họ, nhưng than ôi, bạn sẽ không thể tiến xa được. Vì vậy, để củng cố nền tảng kiến ​​thức của bạn trong lĩnh vực này, tôi muốn nói về một cấu trúc dữ liệu được gọi là kim tự tháp (còn được gọi là heap và heap nhị phân). Theo quy định, các cấu trúc dữ liệu như vậy được sử dụng trong các bộ lập lịch khác nhau và các cấu trúc khác trong đó cần chỉ ra mức độ ưu tiên của các nhiệm vụ khác nhau. Vì vậy... Kim tự tháp là một loại cây cung cấp tính năng chèn/xóa trong thời gian O(logN) và có các thuộc tính sau:

• Sự hoàn thiện. Tất cả các cấp độ của cây đều chứa tất cả các nút có thể ngoại trừ nút cuối cùng, nút này chỉ có thể được điền một phần và được điền từ trái sang phải;
• Kim tự tháp thường được triển khai dựa trên một mảng;
• Đối với mỗi nút trong kim tự tháp, có một điều kiện cơ bản là giá trị của mỗi nút lớn hơn (hoặc bằng) giá trị của các nút con của nó. Theo đó, mức tối đa sẽ được lưu trữ ở phần tử trên cùng.

Một kim tự tháp bao gồm các đỉnh lưu trữ các giá trị không cao hơn 10: Tôi muốn lưu ý rằng so với cây tìm kiếm nhị phân, một kim tự tháp có thứ tự yếu , vì trong cây tìm kiếm nhị phân, khóa của con trái nhỏ hơn khóa chìa khóa của con bên phải, và trong kim tự tháp không có điều kiện như vậy.

Xóa phần tử theo chỉ mục

Trước tiên, hãy xem chuỗi hành động khi xóa nút đã chọn:

1. Xóa nút đã chọn.
2. Di chuyển nút cuối cùng ở hàng cuối cùng đến vị trí của nút đã xóa.
3. Di chuyển nó xuống cho đến khi nó ở dưới nút lớn hơn và phía trên nút nhỏ hơn.

Khi sử dụng kim tự tháp, thông thường cần phải loại bỏ phần trên cùng (phần tử số 0 của mảng bên trong) hoặc phần cuối cùng (khi đó có thể bỏ qua các thao tác di chuyển, chỉ để lại phần loại bỏ phần tử). Như một ví dụ về việc xóa một phần tử theo chỉ mục trong kim tự tháp mà chúng ta đang xem xét ở trên, chúng ta sẽ xóa nút có giá trị 7:

1. Chúng tôi xóa nút đã chọn và đặt nút cuối cùng vào vị trí của nó, có giá trị là 4:

   Nhưng ở vị trí này, nút này không đáp ứng điều kiện là mỗi nút con cháu không được lớn hơn nút được đề cập, phải không?

   Đó là lý do tại sao:

2. Chúng tôi hoán đổi nó với phần tử con lớn nhất, có giá trị là 6:

   Tiếp theo, chúng tôi xem liệu có bất kỳ phần tử con nào có giá trị lớn hơn giá trị của phần tử bị thay thế của chúng tôi hay không và chúng tôi thấy rằng không có phần tử nào, điều đó có nghĩa là phần tử đã chiếm vị trí của nó.

Chèn một phần tử mới

Các hành động khi chèn một phần tử mới là gì:

1. Nút được chèn được đặt ở cuối kim tự tháp.

   Nhưng chúng ta có một điều kiện là phần tử con không được có giá trị lớn hơn phần tử gốc của nó, phải không?

   Đó là lý do tại sao:

2. So sánh phần tử mới với phần tử cha. Nếu phần tử mới nhỏ hơn thì thao tác đã hoàn thành; nếu không, nó sẽ đổi chỗ cho phần tử cha. Sau đó, nó bắt đầu được so sánh với phần tử cha mới, v.v... Cho đến khi phần tử cha lớn hơn phần tử cha mới.

Ví dụ: đối với kim tự tháp có được bằng cách loại bỏ một phần tử, chúng tôi muốn thêm một phần tử có giá trị 8:

1. Đặt một nút mới ở cuối kim tự tháp:

2. So sánh phần tử mới với phần tử cha, phần tử này có giá trị là 4.

   Vì phần tử mới lớn hơn phần tử gốc nên chúng ta hoán đổi chúng:

3. Chúng tôi so sánh phần tử mới với phần tử mẹ mới của nó và thấy rằng phần tử của chúng tôi lớn hơn (8>7), vì vậy chúng tôi cũng hoán đổi chúng:

   Một lần nữa, chúng ta so sánh phần tử với phần tử cha và thấy rằng lần này phần tử cha lớn hơn, điều đó có nghĩa là phần tử mới của chúng ta đã vào đúng vị trí.

Thay thế một phần tử

Khi thay thế một phần tử, trước tiên bạn cần thay thế phần tử đó bằng chỉ mục đã cho. Hợp lý phải không? Vậy tiếp theo là gì? Rốt cuộc, giá trị mới của phần tử đã khác và thực tế không phải là nó tương ứng với các điều kiện của kim tự tháp. Nghĩa là, không phải thực tế là tất cả các phần tử con đều nhỏ hơn phần tử được chèn vào. Thực tế cũng không phải là các phần tử gốc lớn hơn phần tử mới. Vì vậy, trước tiên bạn cần so sánh với giá trị cũ của phần tử:

• nếu phần tử mới lớn hơn nó, thì chúng ta cần so sánh nó với các phần tử gốc và nếu cần, hoán đổi chúng;
• nếu phần tử mới nhỏ hơn thì nó phải được so sánh với phần tử con lớn hơn và hoán đổi nếu phần tử con lớn hơn (cho đến khi phần tử mới ở một vị trí hợp lệ).

Hãy xem xét điều này bằng ví dụ của chúng tôi. Bây giờ chúng tôi muốn chèn một phần tử có giá trị 1 thay vì phần tử có giá trị 9:

1. Chèn phần tử vào vị trí của phần tử trước đó:
2. Chúng ta so sánh phần tử trước 9 và phần tử mới 1 và thấy rằng nó nhỏ hơn, nghĩa là chúng ta sẽ cố gắng dịch chuyển nó xuống.
3. Chúng tôi so sánh nó với phần tử lớn nhất của trẻ em, nghĩa là với phần tử có giá trị 5 và chúng tôi thấy rằng phần tử mới nhỏ hơn. Vì vậy, chúng ta hoán đổi các phần tử được so sánh:
4. Vì bây giờ không có phần tử mới nào bên dưới phần tử mới của chúng tôi nên chúng tôi có thể nói rằng phần tử đó đã vào đúng vị trí.

Triển khai kim tự tháp trong Java

Sau khi hiểu cách cấu trúc này hoạt động, đã đến lúc xem xét cách triển khai kim tự tháp trong Java : Một lớp biểu thị một đỉnh và giá trị mà nó chứa:

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

Lớp đại diện cho kim tự tháp:

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

Cuối cùng, hãy nhìn vào kim tự tháp của chúng ta đang hoạt động:

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

Đầu ra của bảng điều khiển:

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

Đầu ra của bảng điều khiển:

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

Đầu ra của bàn điều khiển: À, chỉ vậy thôi. Cảm ơn tất cả các bạn đã quan tâm!