ڊيٽا جي جوڙجڪ: پرامڊ (بائنري هيپ) جاوا ۾

هاءِ هاءِ! ڪو به انڪار نه ڪندو ته الگورتھم ۽ ڊيٽا ڍانچي پروگرامنگ جي ناقابل ترديد بنياد آهن. ها، توهان انهن کي ڄاڻڻ کان سواء هڪ پروگرامر طور ڪم ڪري سگهو ٿا، پر افسوس، توهان پري نه ويندا. تنهن ڪري، هن علائقي ۾ توهان جي ڄاڻ جي بنياد کي مضبوط ڪرڻ لاء، مان هڪ ڊيٽا جي جوڙجڪ جي باري ۾ ڳالهائڻ چاهيندس جنهن کي پرامڊ سڏيو ويندو آهي (جنهن کي هيپ ۽ بائنري هيپ پڻ سڏيو ويندو آهي). ضابطي جي طور تي، اهڙي ڊيٽا جي جوڙجڪ مختلف شيڊولرز ۽ ٻين جوڙجڪ ۾ استعمال ڪيا ويا آهن جن ۾ مختلف ڪمن جي ترجيحن کي ظاهر ڪرڻ ضروري آهي. تنهن ڪري... هڪ پرامڊ هڪ قسم جو وڻ آهي جيڪو 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. هاڻي کان وٺي اسان جي نئين هيٺان ڪو به نئون عنصر نه آهي، اسان اهو چئي سگهون ٿا ته عنصر پنهنجي جاء تي گر ٿي ويو آهي.

جاوا ۾ هڪ پرامڊ جو نفاذ

سمجھڻ کان پوءِ ھي ڍانچو ڪيئن ڪم ڪري ٿو، اھو وقت آھي جاوا ۾ ھڪ پرامڊ جي عمل کي ڏسڻ لاءِ : ھڪڙو طبقو جيڪو ھڪڙي ورڪس جي نمائندگي ڪري ٿو ۽ ان ۾ شامل قدر:

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

ڪنسول آئوٽ: خير، اهو سڀ ڪجهه آهي. توهان جي ڌيان لاء توهان سڀني جي مهرباني!