ПРИОРИТЕТНА ОПАШКА (СТРУКТУРИ НА ДАННИ)

Приоритетната опашка е абстрактен тип данни, който се държи подобно на нормалната опашка, с изключение на това, че всеки елемент има определен приоритет, т.е. елементът с най-висок приоритет ще бъде първи в приоритетна опашка. Приоритетът на елементите в приоритетната опашка ще определи реда, в който елементите се премахват от приоритетната опашка.

Приоритетната опашка поддържа само сравними елементи, което означава, че елементите са подредени или във възходящ, или в низходящ ред.

как е изобретено училището

Да предположим например, че имаме някои стойности като 1, 3, 4, 8, 14, 22, вмъкнати в опашка с приоритет, като редът, наложен на стойностите, е от най-малкото до най-голямото. Следователно числото 1 ще има най-висок приоритет, докато 22 ще има най-нисък приоритет.

Характеристики на приоритетна опашка

Приоритетна опашка е разширение на опашка, което съдържа следните характеристики:

Всеки елемент в приоритетна опашка има някакъв приоритет, свързан с него.
Елемент с по-висок приоритет ще бъде изтрит преди изтриването на елемент с по-нисък приоритет.
Ако два елемента в една приоритетна опашка имат еднакъв приоритет, те ще бъдат подредени по принципа FIFO.

Нека разберем приоритетната опашка чрез пример.

Имаме опашка с приоритет, която съдържа следните стойности:

1, 3, 4, 8, 14, 22

Всички стойности са подредени във възходящ ред. Сега ще наблюдаваме как ще изглежда приоритетната опашка след извършване на следните операции:

анкета():Тази функция ще премахне елемента с най-висок приоритет от опашката с приоритети. В горната приоритетна опашка елементът '1' има най-висок приоритет, така че ще бъде премахнат от приоритетната опашка.добави (2):Тази функция ще вмъкне елемент '2' в приоритетна опашка. Тъй като 2 е най-малкият елемент сред всички числа, той ще получи най-висок приоритет.анкета():Той ще премахне елемента „2“ от опашката с приоритет, тъй като има опашка с най-висок приоритет.добави (5):Той ще вмъкне 5 елемент след 4, тъй като 5 е по-голямо от 4 и по-малко от 8, така че ще получи третия най-висок приоритет в опашката с приоритети.

Видове приоритетна опашка

Има два вида приоритетна опашка:

Представяне на приоритетна опашка

Сега ще видим как да представим опашката с приоритет чрез еднопосочен списък.

Ще създадем приоритетната опашка, като използваме списъка, даден по-долу, в който ИНФО списъкът съдържа елементите от данни, PRN списъкът съдържа приоритетните номера на всеки елемент от данни, наличен в ИНФО списък, а LINK основно съдържа адреса на следващия възел.

Нека да създадем приоритетната опашка стъпка по стъпка.

tostring java

В случай на опашка с приоритет, номерът с по-нисък приоритет се счита за по-висок приоритет, т.е. номер с по-нисък приоритет = по-висок приоритет.

Етап 1: В списъка номерът с по-нисък приоритет е 1, чиято стойност на данните е 333, така че ще бъде вмъкнат в списъка, както е показано на диаграмата по-долу:

Стъпка 2: След вмъкване на 333, приоритет номер 2 има по-висок приоритет и стойностите на данните, свързани с този приоритет, са 222 и 111. Така че тези данни ще бъдат вмъкнати въз основа на принципа FIFO; следователно първо ще бъдат добавени 222 и след това 111.

Стъпка 3: След вмъкване на елементите с приоритет 2, следващото число с по-висок приоритет е 4, а елементите от данни, свързани с 4 номера на приоритет, са 444, 555, 777. В този случай елементите ще бъдат вмъкнати въз основа на принципа FIFO; следователно първо ще бъдат добавени 444, след това 555 и след това 777.

Стъпка 4: След вмъкване на елементите с приоритет 4, следващото число с по-висок приоритет е 5, а стойността, свързана с приоритет 5, е 666, така че ще бъде вмъкнато в края на опашката.

Внедряване на приоритетна опашка

Приоритетната опашка може да бъде реализирана по четири начина, които включват масиви, свързан списък, структура от данни в купчина и двоично дърво за търсене. Heap структурата от данни е най-ефективният начин за внедряване на приоритетната опашка, така че в тази тема ще внедрим приоритетната опашка с помощта на heap структура от данни. Сега, първо разбираме причината, поради която купчината е най-ефективният начин сред всички останали структури от данни.

Анализ на сложностите с помощта на различни реализации

Внедряване	добавете	Премахване	надниквам
Свързан списък	О(1)	На)	На)
Двоична купчина	O(вход)	O(вход)	О(1)
Двоично дърво за търсене	O(вход)	O(вход)	О(1)

Какво е Heap?

Купчината е дървовидна структура от данни, която образува цялостно двоично дърво и отговаря на свойството за купчина. Ако A е родителски възел на B, тогава A е подреден по отношение на възел B за всички възли A и B в купчина. Това означава, че стойността на родителския възел може да бъде по-голяма или равна на стойността на дъщерния възел или стойността на родителския възел може да бъде по-малка или равна на стойността на дъщерния възел. Следователно можем да кажем, че има два вида купчини:

И двете купчини са двоична купчина, тъй като всяка има точно два дъщерни възела.

Операции с приоритетна опашка

Общите операции, които можем да изпълняваме върху приоритетна опашка, са вмъкване, изтриване и надникване. Нека да видим как можем да поддържаме структурата на купчини данни.

Вмъкване на елемента в опашка с приоритет (максимален обем)

Ако вмъкнем елемент в приоритетна опашка, той ще се премести в празния слот, като погледнем отгоре надолу и отляво надясно.

Ако елементът не е на правилното място, той се сравнява с родителския възел; ако се установи, че не е в ред, елементите се разменят. Този процес продължава, докато елементът не бъде поставен в правилна позиция.

Премахване на минималния елемент от приоритетната опашка

Както знаем, че в максимален куп, максималният елемент е коренният възел. Когато премахнем основния възел, той създава празен слот. Последният вмъкнат елемент ще бъде добавен в този празен слот. След това този елемент се сравнява с дъщерните възли, т.е. ляво дете и дясно дете, и се разменя с по-малкия от двата. Продължава да се движи надолу по дървото, докато не се възстанови свойството на купчината.

Приложения на приоритетна опашка

Следните са приложенията на приоритетната опашка:

подчертаване подчертаване

Използва се в алгоритъма за най-краткия път на Дейкстра.
Използва се в алгоритъма на прим
Използва се в техники за компресиране на данни като код на Хъфман.
Използва се при групово сортиране.
Използва се и в операционната система като приоритетно планиране, балансиране на натоварването и обработка на прекъсвания.

Програма за създаване на приоритетна опашка с помощта на двоичната максимална купчина.

 #include #include int heap[40]; int size=-1; // retrieving the parent node of the child node int parent(int i) { return (i - 1) / 2; } // retrieving the left child of the parent node. int left_child(int i) { return i+1; } // retrieving the right child of the parent int right_child(int i) { return i+2; } // Returning the element having the highest priority int get_Max() { return heap[0]; } //Returning the element having the minimum priority int get_Min() { return heap[size]; } // function to move the node up the tree in order to restore the heap property. void moveUp(int i) { while (i &gt; 0) { // swapping parent node with a child node if(heap[parent(i)] <heap[i]) 2 { int temp; temp="heap[parent(i)];" heap[parent(i)]="heap[i];" heap[i]="temp;" } updating the value of i to function move node down tree in order restore heap property. void movedown(int k) index="k;" getting location left child if (left heap[index]) right (right k is not equal (k !="index)" heap[index]="heap[k];" heap[k]="temp;" movedown(index); removing element maximum priority removemax() r="heap[0];" heap[0]="heap[size];" size="size-1;" movedown(0); inserting a queue insert(int p) + 1; heap[size]="p;" up maintain property moveup(size); from at given i. delete(int i) stored ith shifted root moveup(i); having removemax(); main() elements insert(20); insert(19); insert(21); insert(18); insert(12); insert(17); insert(15); insert(16); insert(14); printf('elements are : '); for(int printf('%d ',heap[i]); delete(2); deleting whose 2. printf('
elements after max="get_Max();" printf('
the which highest %d: ',max); min="get_Min();" minimum %d',min); return 0; < pre> <p> <strong>In the above program, we have created the following functions:</strong> </p> <ul> <tr><td>int parent(int i):</td> This function returns the index of the parent node of a child node, i.e., i. </tr><tr><td>int left_child(int i):</td> This function returns the index of the left child of a given index, i.e., i. </tr><tr><td>int right_child(int i):</td> This function returns the index of the right child of a given index, i.e., i. </tr><tr><td>void moveUp(int i):</td> This function will keep moving the node up the tree until the heap property is restored. </tr><tr><td>void moveDown(int i):</td> This function will keep moving the node down the tree until the heap property is restored. </tr><tr><td>void removeMax():</td> This function removes the element which is having the highest priority. </tr><tr><td>void insert(int p):</td> It inserts the element in a priority queue which is passed as an argument in a function <strong>.</strong>  </tr><tr><td>void delete(int i):</td> It deletes the element from a priority queue at a given index. </tr><tr><td>int get_Max():</td> It returns the element which is having the highest priority, and we know that in max heap, the root node contains the element which has the largest value, and highest priority. </tr><tr><td>int get_Min():</td> It returns the element which is having the minimum priority, and we know that in max heap, the last node contains the element which has the smallest value, and lowest priority. </tr></ul> <p> <strong>Output</strong> </p> <img src="//techcodeview.com/img/ds-tutorial/03/what-is-priority-queue-9.webp" alt="Priority Queue"> <hr></heap[i])>

TechCodeview

Какво е приоритетна опашка?