ساختارهای داده: هرمی (هپ باینری) در جاوا

سلام سلام! هیچ کس انکار نمی کند که الگوریتم ها و ساختارهای داده پایه غیرقابل انکار برنامه نویسی هستند. بله، شما می توانید بدون شناخت آنها به عنوان یک برنامه نویس کار کنید، اما افسوس که دور از دسترس نخواهید بود. بنابراین، برای تقویت پایگاه دانش شما در این زمینه، می خواهم در مورد ساختار داده ای به نام هرم (همچنین به عنوان هیپ و هیپ باینری) صحبت کنم. به عنوان یک قاعده، چنین ساختارهای داده ای در زمانبندی های مختلف و سایر ساختارها استفاده می شود که در آنها لازم است اولویت وظایف مختلف مشخص شود. بنابراین... هرم نوعی درخت است که درج/حذف را در زمان 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. از آنجایی که اکنون هیچ عنصر جدیدی زیر عنصر جدید ما وجود ندارد، می توان گفت که عنصر در جای خود قرار گرفته است.

پیاده سازی هرم در جاوا

پس از درک نحوه عملکرد این ساختار، وقت آن است که به پیاده سازی یک هرم در جاوا نگاه کنیم : کلاسی که یک راس را نشان می دهد و مقدار آن را نشان می دهد:

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

خروجی کنسول: خب، همین. با تشکر از همه شما برای توجه شما!