ڈیٹا سٹرکچرز: جاوا میں اہرام (بائنری ہیپ)

ہائے ہائے! کوئی بھی اس سے انکار نہیں کرے گا کہ الگورتھم اور ڈیٹا سٹرکچر پروگرامنگ کی ناقابل تردید بنیاد ہیں۔ جی ہاں، آپ ان کو جانے بغیر ایک پروگرامر کے طور پر کام کر سکتے ہیں، لیکن افسوس، آپ زیادہ دور نہیں جائیں گے۔ لہذا، اس علاقے میں آپ کے علم کی بنیاد کو مضبوط کرنے کے لیے، میں ایک ڈیٹا سٹرکچر کے بارے میں بات کرنا چاہوں گا جسے اہرام کہتے ہیں (جسے ہیپ اور بائنری ہیپ بھی کہا جاتا ہے)۔ ایک اصول کے طور پر، اس طرح کے ڈیٹا ڈھانچے کو مختلف شیڈولرز اور دیگر ڈھانچے میں استعمال کیا جاتا ہے جس میں مختلف کاموں کی ترجیح کی نشاندہی کرنا ضروری ہے۔ تو... ایک اہرام درخت کی ایک قسم ہے جو 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();
  }
}

کنسول آؤٹ پٹ: ٹھیک ہے، بس اتنا ہی ہے۔ آپ کی توجہ کے لیے آپ سب کا شکریہ!