データ構造: Java のピラミッド (バイナリ ヒープ)

こんにちは、こんにちは！アルゴリズムとデータ構造がプログラミングの紛れもない基礎であることを否定する人はいません。確かに、プログラマーの知識がなくてもプログラマーとして働くことはできますが、残念ながら、そこまでは進みません。したがって、この分野の知識ベースを強化するために、ピラミッド(ヒープやバイナリ ヒープとも呼ばれる)などのデータ構造について説明したいと思います。一般に、そのようなデータ構造は、さまざまなタスクの優先順位を示す必要があるさまざまなスケジューラやその他の構造で使用されます。つまり...ピラミッドは、O(logN)時間で挿入/削除を行うツリーの一種であり、次の特性があります。

• 完全。ツリーのすべてのレベルには、最後のノードを除くすべての可能なノードが含まれます。最後のノードは部分的にしか埋めることができず、左から右に埋められます。
• ピラミッドは通常、配列に基づいて実装されます。
• ピラミッド内の各ノードには、各ノードの値がその子孫の値より大きい (または等しい) という基本条件があります。したがって、最大値は先頭の要素に格納されます。

10 以下の値を格納する頂点で構成されるピラミッド:二分探索ツリーと比較して、ピラミッドは弱い順序付けであることに注意してください。これは、二分探索ツリーでは左側の子のキーがそのキーよりも小さいためです。右側の子のキーですが、ピラミッドではそのような条件はありません。

インデックスによる要素の削除

まず、選択したノードを削除するときの一連のアクションを見てみましょう。

1. 選択したノードを削除します。
2. 最後の行の最後のノードを、削除されたノードの場所に移動します。
3. 大きいノードの下、小さいノードの上になるまで下に移動します。

ピラミッドを使用する場合、通常は先頭 (内部配列のゼロ要素) または最後の要素を削除できる必要があります (そうすれば、移動操作を省略して、要素の削除のみを残すことができます)。上で見ているピラミッド内のインデックスによって要素を削除する例として、値 7 のノードを削除します。

1. 選択したノードを削除し、値 4 を持つ最後のノードをその場所に配置します。

   しかし、この位置では、このノードは、各子孫ノードが問題のノードより大きくてはならないという条件を満たしていませんよね?

   それが理由です：

2. これを、値 6 を持つ最大の子の値と交換します。

   次に、移動した要素の値よりも大きい値を持つ子孫が存在するかどうかを確認しますが、何も存在しないことがわかります。これは、要素が代わりに配置されたことを意味します。

新しい要素の挿入

新しい要素を挿入するときのアクションは次のとおりです。

1. 挿入されたノードはピラミッドの端に配置されます。

   ただし、子要素には親より大きい値を設定できないという条件がありますよね?

   それが理由です：

2. 新しい要素を親要素と比較します。新しい要素が小さい場合は操作が完了し、そうでない場合は親要素と位置を交換します。その後、新しい親要素との比較が開始され、親要素が新しい親要素よりも大きくなるまで繰り返されます。

たとえば、要素を削除して得られたピラミッドに、値 8 の要素を追加したいとします。

1. ピラミッドの最後に新しいノードを配置します。

2. 新しい要素を、値 4 を持つ親要素と比較します。

   新しい要素は親よりも大きいため、それらを交換します。

3. 新しい要素とその新しい親を比較すると、要素がその要素より大きい (8>7) ことがわかります。そのため、それらも交換します。

   もう一度、要素を親要素と比較すると、今回は親要素の方が大きいことがわかります。これは、新しい要素が所定の位置に収まったことを意味します。

要素の交換

要素を置き換える場合は、まず要素を指定されたインデックスで置き換える必要があります。論理的ですよね？それで、次は何でしょうか？結局のところ、要素の新しい値はすでに異なっており、それがピラミッドの条件に対応しているかどうかは事実ではありません。つまり、すべての子要素が挿入された要素よりも小さいということは事実ではありません。親要素が新しい要素よりも大きいということも事実ではありません。したがって、最初に要素の古い値と比較する必要があります。

• 新しい要素がそれよりも大きい場合は、それを親要素と比較し、必要に応じてそれらを交換する必要があります。
• 新しい要素が小さい場合は、大きい方の子要素と比較し、子要素の方が大きい場合は交換する必要があります (新しい要素が有効な場所に配置されるまで)。

例を使用してこれを見てみましょう。ここで、値 9 の要素の代わりに値 1 の要素を挿入します。

1. 前の要素の代わりに要素を挿入します。
2. 前の要素 9 と新しい要素 1 を比較すると、それが小さいことがわかります。これは、それを下にシフトしようとすることを意味します。
3. これを子の要素の最大の要素、つまり値が 5 の要素と比較すると、新しい要素の方が小さいことがわかります。したがって、比較される要素を交換します。
4. 新しい要素の下に新しい要素はないので、要素は適切な位置に収まったと言えます。

Java でのピラミッドの実装

この構造がどのように機能するかを理解したら、 Java でのピラミッドの実装を見てみましょう。1 つの頂点とそれに含まれる値を表すクラスです。

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

コンソール出力:まあ、それだけです。ご清聴ありがとうございました！