数据结构：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();
  }
}

控制台输出：好了，就这些了。感谢大家的关注！