Ma'lumotlar tuzilmalari: Java-da piramida (ikkilik uyasi).

Salom salom! Algoritmlar va ma'lumotlar tuzilmalari dasturlashning inkor etilmaydigan asosi ekanligini hech kim inkor etmaydi. Ha, siz ularni bilmagan holda dasturchi bo'lib ishlashingiz mumkin, lekin afsuski, siz uzoqqa bormaysiz. Shuning uchun, ushbu sohadagi bilim bazangizni mustahkamlash uchun men piramida deb ataladigan ma'lumotlar tuzilmasi (uyma va ikkilik uyum sifatida ham tanilgan) haqida gapirmoqchiman . Qoida tariqasida, bunday ma'lumotlar tuzilmalari turli xil rejalashtiruvchilar va boshqa tuzilmalarda qo'llaniladi, ularda turli vazifalarning ustuvorligini ko'rsatish kerak. Shunday qilib... Piramida O(logN) vaqtida kiritish/oʻchirishni taʼminlovchi va quyidagi xususiyatlarga ega boʻlgan daraxt turidir :

• To'liqlik. Daraxtning barcha darajalari oxirgisidan tashqari barcha mumkin bo'lgan tugunlarni o'z ichiga oladi, ular faqat qisman to'ldirilishi mumkin va chapdan o'ngga to'ldiriladi;
• Piramida odatda massiv asosida amalga oshiriladi;
• Piramidadagi har bir tugun uchun har bir tugunning qiymati uning avlodlari qiymatlaridan kattaroq (yoki teng) bo'lishining asosiy sharti mavjud. Shunga ko'ra, maksimal yuqori elementda saqlanadi.

10 dan yuqori bo'lmagan qiymatlarni saqlaydigan cho'qqilardan iborat piramida: Shuni ta'kidlashni istardimki, ikkilik qidiruv daraxti bilan solishtirganda, piramida zaif tartiblangan , chunki ikkilik qidiruv daraxtida chap bolaning kaliti kichikroqdir. o'ng bolaning kaliti va piramidada bunday shart yo'q.

Indeks bo'yicha elementni olib tashlash

Birinchidan, tanlangan tugunni o'chirishda harakatlar ketma-ketligini ko'rib chiqaylik:

1. Tanlangan tugunni o'chiring.
2. Oxirgi qatordagi oxirgi tugunni o'chirilgan joyga ko'chiring.
3. Kattaroq va kichikroq tugunning ustida bo'lguncha uni pastga siljiting.

Piramidadan foydalanganda, odatda, yuqori qismini (ichki massivning nol elementi) yoki oxirgi qismini (keyin elementni olib tashlashni qoldirib, harakatlanuvchi operatsiyalarni o'tkazib yuborish mumkin) olib tashlash imkoniyatiga ega bo'lish kerak. Yuqorida ko'rib chiqilayotgan piramidadagi elementni indeks bo'yicha o'chirishga misol sifatida biz 7 qiymatiga ega tugunni o'chirib tashlaymiz:

1. Biz tanlangan tugunni o'chirib tashlaymiz va uning o'rniga 4 qiymatiga ega bo'lgan oxirgisini joylashtiramiz:

   Ammo bu holatda, bu tugun har bir nasl tugunining ko'rib chiqilayotganidan kattaroq bo'lmasligi shartiga javob bermaydi, to'g'rimi?

   Shunung uchun:

2. Biz uni bolalarning eng kattasi bilan almashtiramiz, uning qiymati 6 ga teng:

   Keyinchalik, biz almashtirilgan elementimizdan kattaroq qiymatga ega bo'lgan avlodlar bor yoki yo'qligini tekshiramiz va ularning yo'qligini ko'ramiz, bu element o'z o'rnini egallaganligini anglatadi.

Yangi element kiritish

Yangi elementni kiritishda qanday harakatlar amalga oshiriladi:

1. Kiritilgan tugun piramidaning oxiriga joylashtiriladi.

   Lekin bizda shunday shart borki, bola elementi ota-onasidan kattaroq qiymatga ega bo'lolmaydi, to'g'rimi?

   Shunung uchun:

2. Yangi elementni asosiy element bilan solishtiring. Agar yangi element kichikroq bo'lsa, u holda operatsiya yakunlanadi, agar bo'lmasa, u asosiy element bilan joylarni almashtiradi. Shundan so'ng, u yangi asosiy element bilan taqqoslana boshlaydi va hokazo ... Ota element yangidan kattaroq bo'lmaguncha.

Masalan, elementni olib tashlash orqali olingan piramidaga biz 8 qiymatiga ega elementni qo'shmoqchimiz:

1. Piramidaning oxiriga yangi tugun qo'ying:

2. Yangi elementni 4 qiymatiga ega bo'lgan asosiy element bilan solishtiring.

   Yangi element asosiy elementdan kattaroq bo'lgani uchun biz ularni almashtiramiz:

3. Biz yangi elementni uning yangi ota-onasi bilan solishtiramiz va bizning elementimiz uning (8>7) dan kattaroq ekanligini ko'ramiz, shuning uchun ularni ham almashtiramiz:

   Yana, biz elementni asosiy element bilan solishtiramiz va bu safar asosiy element kattaroq ekanligini ko'ramiz, bu bizning yangi elementimiz joyiga tushganligini anglatadi.

Elementni almashtirish

Elementni almashtirishda birinchi navbatda elementni berilgan indeks bilan almashtirish kerak. Mantiqiy, to'g'rimi? Xo'sh, keyin nima? Axir, elementning yangi qiymati allaqachon boshqacha va u piramida shartlariga mos kelishi haqiqat emas. Ya'ni, barcha asosiy elementlar kiritilgan elementdan kichikroq ekanligi haqiqat emas. Bundan tashqari, ota-ona elementlari yangidan kattaroq ekanligi haqiqat emas. Shuning uchun, avval elementning eski qiymati bilan solishtirishingiz kerak:

• agar yangi element undan kattaroq bo'lsa, biz uni asosiy elementlar bilan taqqoslashimiz va kerak bo'lganda ularni almashtirishimiz kerak;
• agar yangi element kichikroq bo'lsa, u holda uni eng katta elementlar bilan solishtirish va agar kichik element kattaroq bo'lsa, almashtirish kerak (yangi element maqbul joyda bo'lgunga qadar).

Keling, buni misolimizdan foydalanib ko'rib chiqaylik. Endi biz 9-qiymatli element oʻrniga 1-qiymatli elementni kiritmoqchimiz:

1. Elementni oldingi o'rniga qo'ying:
2. Biz oldingi element 9 va yangi 1 ni solishtiramiz va uning kichikroq ekanligini ko'ramiz, ya'ni biz uni pastga siljitishga harakat qilamiz.
3. Biz uni bolalarning eng katta elementi bilan, ya'ni qiymati 5 ga teng bo'lgan element bilan taqqoslaymiz va biz yangisi kichikroq ekanligini ko'ramiz. Shunday qilib, biz taqqoslangan elementlarni almashtiramiz:
4. Hozir bizning yangi elementimiz ostida hech qanday yangi elementlar yo'qligi sababli, element o'rniga tushib qolgan deb aytishimiz mumkin.

Java-da piramidani amalga oshirish

Ushbu tuzilma qanday ishlashini tushunganingizdan so'ng, Java-da piramidani amalga oshirishni ko'rib chiqish vaqti keldi : Bir tepalikni ifodalovchi sinf va u o'z ichiga olgan qiymat:

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

Piramidaning o'zini ifodalovchi sinf:

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
  }
}

Nihoyat, piramidamizning harakatini ko'rib chiqaylik:

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

Konsol chiqishi:

// изменяем элемент под индексом 0 с 210 на 15, и выводим в консоль измененную пирамиду
     heap.changeNode(0,15);
     heap.printHeap();

Konsol chiqishi:

// удаляем элемент под индексом 3, который имеет meaning 80 и смотрим на изменившуюся пирамиду
     heap.removeNode(3);
     heap.printHeap();
  }
}

Konsol chiqishi: Xo'sh, hammasi shu. E'tiboringiz uchun barchangizga rahmat!