โครงสร้างข้อมูล: พีระมิด (Binary Heap) ใน 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();
  }
}

เอาต์พุตคอนโซล: นั่นคือทั้งหมด ขอขอบคุณทุกท่านที่ให้ความสนใจ!