Комилан. Ҳама сатҳҳои дарахт ҳама гиреҳҳои имконпазирро дар бар мегиранд, ба истиснои охирин, ки танҳо қисман пур карда мешаванд ва аз чап ба рост пур карда мешаванд;
Барои ҳар як гиреҳ дар пирамида шарти асосӣ мавҷуд аст, ки арзиши ҳар як гиреҳ аз арзишҳои насли он бузургтар (ё баробар) бошад. Мувофиқи он, ҳадди аксар дар элементи боло нигоҳ дошта мешавад.
Пирамида, ки аз қуллаҳое иборат аст, ки арзишҳоро на бештар аз 10 нигоҳ медоранд: Ман мехоҳам қайд намоям, ки дар муқоиса бо дарахти ҷустуҷӯии дуӣ, пирамида суст тартиб дода шудааст , зеро дар дарахти ҷустуҷӯи бинарӣ калиди кӯдаки чап аз он камтар аст. калиди кӯдаки рост ва дар пирамида чунин шароит вуҷуд надорад.
Аммо мо як шарт дорем, ки унсури кӯдак наметавонад аз волидайни худ арзиши бузургтар дошта бошад, дуруст?
Барои ҳамон:
Унсури навро бо унсури волидайн муқоиса кунед. Агар элементи нав хурдтар бошад, пас амалиёт анҷом мешавад, агар не, он ҷойҳоро бо элементи волидайн иваз мекунад. Пас аз ин, он бо унсури нави волидайн муқоиса карда мешавад ва ғайра... То он даме, ки унсури волидайн аз нав бузургтар бошад.
Масалан, ба пирамидае, ки тавассути нест кардани элемент ба даст оварда шудааст, мо мехоҳем элементеро бо арзиши 8 илова кунем:
Пас аз фаҳмидани он, ки ин сохтор чӣ гуна кор мекунад, вақти он расидааст, ки ба татбиқи пирамида дар Java назар кунем : Синф, ки як қулла ва арзиши онро дар бар мегирад:
publicclassHeap{privateNode[] heapArray;// массив со всеми вершинамиprivateint maxSize;// размер массиваprivateint currentSize;// количество узлов массивеpublicHeap(int maxSize){// создание пустой пирамидыthis.maxSize = maxSize;this.currentSize =0;
heapArray =newNode[maxSize];}publicvoidprintHeap(){// отображение перамиды в консоль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);// нижний пункир}publicbooleaninsertNode(int value){// вставка нового значенияif(currentSize == maxSize){// проверяем не выходим ли мы за рамки массиваreturnfalse;}Node newNode =newNode(value);// создание вершины с данным meaningм
heapArray[currentSize]= newNode;// вершину задём в самый низ дереваdisplaceUp(currentSize++);// пытаемся поднять вершину, если meaning вершины позволяетreturntrue;}publicNoderemoveNode(int index){// удалить элемент по индексу массиваif(index >0&& currentSize > index){Node root = heapArray[index];
heapArray[index]= heapArray[--currentSize];// задаём элементу с переданным индексом, meaning последнего element
heapArray[currentSize]=null;// последний элемент удаляемdisplaceDown(index);// проталкиваем вниз новый элемент, чтобы он должное ему местоreturn root;}returnnull;}publicbooleanchangeNode(int index,int newValue){if(index <0|| currentSize<=index){returnfalse;}int oldValue = heapArray[index].getValue();// сохраняем старое meaning
heapArray[index].setValue(newValue);// присваиваем новоеif(oldValue < newValue){// если узел повышаетсяdisplaceUp(index);// выполняется смещение вверх}else{// если понижаетсяdisplaceDown(index);// смещение вниз}returntrue;}privatevoiddisplaceUp(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;// соохраняем результат}privatevoiddisplaceDown(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}}
Ман мехоҳам қайд намоям, ки дар муқоиса бо дарахти ҷустуҷӯии дуӣ, пирамида суст тартиб дода шудааст , зеро дар дарахти ҷустуҷӯи бинарӣ калиди кӯдаки чап аз он камтар аст. калиди кӯдаки рост ва дар пирамида чунин шароит вуҷуд надорад.
Бале, ин ҳама аст. Ташаккур ба ҳама барои таваҷҷӯҳатон!
GO TO FULL VERSION