資料結構：Java 中的金字塔（二元堆）

嗨嗨！沒有人會否認演算法和資料結構是程式設計不可否認的基礎。是的，你可以在沒有他們知識的情況下成為一名程式設計師，但可惜的是，你不會走得太遠。因此，為了加強你在這方面的知識基礎，我想談談像金字塔（也稱為堆和二元堆）這樣的資料結構。通常，這樣的資料結構被用在各種調度器和其他需要指示各種任務的優先順序的結構中。所以...金字塔是一種樹，可以在O(logN)時間內提供插入/刪除，並具有以下屬性：

• 完整性。樹的所有層都包含除最後一個節點之外的所有可能的節點，最後一個節點只能部分填充，並且從左到右填充；
• 金字塔通常是基於數組實現的；
• 對於金字塔中的每個節點，有一個基本條件，即每個節點的值大於（或等於）其後代的值。因此，最大值將儲存在頂部元素中。

由儲存值不高於 10 的頂點組成的金字塔：我想指出的是，與二元搜尋樹相比，金字塔是弱有序的，因為在二元搜尋樹中，左子節點的鍵小於右孩子的鑰匙，而在金字塔中則不存在這種情況。

按索引刪除元素

首先，讓我們來看看刪除選定節點時的操作順序：

1. 刪除選定的節點。
2. 將最後一行的最後一個節點移到刪除節點的位置。
3. 向下移動它，直到它位於較大節點的下方和較小節點的上方。

使用金字塔時，通常需要能夠移除頂部（內部陣列的零元素）或最後一個（那麼可以省略移動操作，只留下元素的移除）。作為我們在上面查看的金字塔中按索引刪除元素的範例，我們將刪除值為 7 的節點：

1. 我們刪除選定的節點並將最後一個節點放在其位置上，該節點的值為 4：

   但在這個位置上，這個節點不滿足每個後代節點不應該大於所討論的節點的條件，對吧？

   這就是為什麼：

2. 我們將它與最大的子項交換，其值為 6：

   接下來，我們查看是否有任何後代的值大於被替換元素的值，我們發現沒有，這意味著該元素已經取代了它的位置。

插入新元素

插入新元素時有哪些操作：

1. 插入的節點放置在金字塔的末端。

   但是我們有一個條件，子元素的值不能大於其父元素，對嗎？

   這就是為什麼：

2. 將新元素與父元素進行比較。如果新元素較小，則操作完成；如果較小，則與父元素交換位置。之後就開始和新的父元素進行比較，以此類推……直到父元素大於新的元素。

例如，對於刪除一個元素得到的金字塔，我們要新增一個值為 8 的元素：

1. 在金字塔的末端放置一個新節點：

2. 將新元素與父元素進行比較，父元素的值為 4。

   由於新元素比父元素大，我們交換它們：

3. 我們將新元素與其新父元素進行比較，發現我們的元素比它大（8>7），因此我們也交換它們：

   再次，我們將該元素與父元素進行比較，發現這次父元素更大，這意味著我們的新元素已經就位。

替換元素

替換元素時，首先需要用給定的索引來取代該元素。符合邏輯，對吧？那接下來怎麼辦？畢竟元素的新值已經不同了，符合金字塔的條件並不是事實。也就是說，並非所有子元素都小於插入元素。父元素比新元素大也不是事實。因此，首先需要與元素的舊值進行比較：

• 如果新元素比它大，那麼我們需要將它與父元素進行比較，並在必要時交換它們；
• 如果新元素較小，則必須將其與較大的子元素進行比較，如果子元素較大則交換（直到新元素位於可接受的位置）。

讓我們用我們的例子來看看這個。現在我們要插入一個值為 1 的元素，而不是一個值為 9 的元素：

1. 插入該元素代替前一個元素：
2. 我們比較前一個元素 9 和新元素 1 ，發現它更小，這意味著我們將嘗試將其向下移動。
3. 我們將它與子元素中最大的元素（即值為 5 的元素）進行比較，我們發現新元素較小。因此，我們交換比較的元素：
4. 由於現在新元素下面沒有新元素，我們可以說該元素已經就位。

Java中金字塔的實現

在了解了這個結構的工作原理後，是時候看看Java 中金字塔的實作了：一個代表一個頂點及其包含的值的類別：

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

控制台輸出：好了，就這些了。感謝大家的關注！