데이터 구조: Java의 피라미드(이진 힙)

안녕 안녕! 알고리즘과 데이터 구조가 프로그래밍의 확실한 기초라는 사실을 누구도 부인하지 않을 것입니다. 예, 당신은 그들의 지식 없이도 프로그래머로 일할 수 있지만 아쉽게도 멀리 갈 수는 없습니다. 따라서 이 분야에 대한 지식 기반을 강화하기 위해 피라미드 (힙 및 바이너리 힙이라고도 함) 와 같은 데이터 구조에 대해 이야기하고 싶습니다 . 일반적으로 이러한 데이터 구조는 다양한 작업의 우선 순위를 나타내는 데 필요한 다양한 스케줄러 및 기타 구조에 사용됩니다. 그래서... 피라미드는 O(logN) 시간 에 삽입/삭제를 제공하는 트리 유형이며 다음과 같은 속성을 갖습니다.

• 완전성. 트리의 모든 수준에는 부분적으로만 채워질 수 있고 왼쪽에서 오른쪽으로 채워지는 마지막 노드를 제외하고 가능한 모든 노드가 포함됩니다.
• 피라미드는 일반적으로 배열을 기반으로 구현됩니다.
• 피라미드의 각 노드에는 각 노드의 값이 해당 하위 노드의 값보다 크거나 같다는 기본 조건이 있습니다. 따라서 최대값은 최상위 요소에 저장됩니다.

10보다 높지 않은 값을 저장하는 정점으로 구성된 피라미드: 이진 검색 트리에 비해 피라미드의 순서가 약하다 는 점에 주목하고 싶습니다. 이진 검색 트리에서는 왼쪽 자식의 키가 올바른 자식의 키이며 피라미드에는 그러한 조건이 없습니다.

인덱스로 요소 제거

먼저 선택한 노드를 삭제할 때의 작업 순서를 살펴보겠습니다.

1. 선택한 노드를 삭제합니다.
2. 마지막 행의 마지막 노드를 삭제된 위치로 이동합니다.
3. 더 큰 노드 아래와 작은 노드 위에 올 때까지 아래로 이동합니다.

피라미드를 사용할 때 일반적으로 맨 위(내부 배열의 0 요소) 또는 마지막 요소(이동 작업은 생략하고 요소 제거만 남길 수 있음)를 제거할 수 있어야 합니다. 위에서 보고 있는 피라미드에서 인덱스별로 요소를 삭제하는 예로서 값이 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에서 피라미드의 구현을 살펴보겠습니다 . 하나의 꼭지점과 여기에 포함된 값을 나타내는 클래스는 다음과 같습니다.

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

콘솔 출력: 그게 다입니다. 관심을 가져주셔서 감사합니다!