מבני נתונים: פירמידה (ערימה בינארית) ב-Java

היי היי! אף אחד לא יכחיש שאלגוריתמים ומבני נתונים הם הבסיס הבלתי מעורער של התכנות. כן, אתה יכול לעבוד כמתכנת מבלי להכיר אותם, אבל אבוי, לא תגיע רחוק. לכן, כדי לחזק את בסיס הידע שלכם בתחום זה, ברצוני לדבר על מבנה נתונים הנקרא פירמידה (הידוע גם כ-heap ו-binary heap). ככלל, מבני נתונים כאלה משמשים מתזמנים שונים ובמבנים אחרים שבהם יש צורך לציין את העדיפות של משימות שונות. אז... פירמידה היא סוג של עץ המספק הכנסה/מחיקה בזמן 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 : מחלקה המייצגת קודקוד אחד ואת הערך שהיא מכילה:

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

פלט מסוף: ובכן, זה הכל. תודה לכולכם על תשומת הלב!