Приоритетни ред је апстрактни тип података који се понаша слично нормалном реду, осим што сваки елемент има неки приоритет, тј. елемент са највишим приоритетом би био први у реду приоритета. Приоритет елемената у приоритетном реду ће одредити редослед којим се елементи уклањају из приоритетног реда.
Приоритетни ред подржава само упоредиве елементе, што значи да су елементи распоређени у растућем или опадајућем редоследу.
јава изузеци
На пример, претпоставимо да имамо неке вредности као што су 1, 3, 4, 8, 14, 22 уметнуте у приоритетни ред са редоследом наметнутим вредностима од најмање до највеће. Према томе, број 1 би имао највећи приоритет, док ће 22 имати најнижи приоритет.
Карактеристике приоритетног реда
Приоритетни ред је проширење реда које садржи следеће карактеристике:
- Сваки елемент у приоритетном реду има неки приоритет повезан са њим.
- Елемент са вишим приоритетом биће обрисан пре брисања мањег приоритета.
- Ако два елемента у приоритетном реду имају исти приоритет, они ће бити распоређени по ФИФО принципу.
Хајде да разумемо приоритетни ред кроз пример.
Имамо приоритетни ред који садржи следеће вредности:
1, 3, 4, 8, 14, 22
Све вредности су распоређене у растућем редоследу. Сада ћемо посматрати како ће приоритетни ред изгледати након извођења следећих операција:
Типови приоритетних редова
Постоје две врсте приоритетног реда:
Представљање приоритетног реда
Сада ћемо видети како да представимо приоритетни ред кроз једносмерну листу.
Направићемо приоритетни ред користећи доле дату листу у којој ИНФО листа садржи елементе података, ПРН листа садржи приоритетне бројеве сваког елемента података који је доступан у ИНФО листа, а ЛИНК у основи садржи адресу следећег чвора.
Хајде да креирамо приоритетни ред корак по корак.
јава сортирање низа
У случају редоследа приоритета, број нижег приоритета се сматра вишим приоритетом, тј. број нижег приоритета = виши приоритет.
Корак 1: У листи, број нижег приоритета је 1, чија је вредност података 333, тако да ће бити убачен у листу као што је приказано на дијаграму испод:
Корак 2: Након уметања 333, приоритет број 2 има већи приоритет, а вредности података повезане са овим приоритетом су 222 и 111. Дакле, ови подаци ће бити уметнути на основу ФИФО принципа; стога ће се прво додати 222, а затим 111.
Корак 3: Након уметања елемената приоритета 2, следећи већи приоритетни број је 4, а елементи података придружени 4 приоритетна броја су 444, 555, 777. У овом случају, елементи би се убацивали на основу ФИФО принципа; стога ће се прво додати 444, затим 555, а затим 777.
4. корак: Након уметања елемената приоритета 4, следећи већи број приоритета је 5, а вредност придружена приоритету 5 је 666, тако да ће бити уметнута на крају реда.
Имплементација приоритетног реда
Приоритетни ред се може имплементирати на четири начина који укључују низове, повезану листу, структуру података у хрпи и стабло бинарног претраживања. Структура података гомиле је најефикаснији начин имплементације приоритетног реда, тако да ћемо у овој теми имплементирати приоритетни ред користећи структуру података гомиле. Сада, прво разумемо разлог зашто је хрпа најефикаснији начин међу свим осталим структурама података.
Анализа сложености коришћењем различитих имплементација
| Имплементација | додати | Уклони | завирити |
| Повезана листа | О(1) | На) | На) |
| Бинарна гомила | О(пријава) | О(пријава) | О(1) |
| Бинарно стабло претраге | О(пријава) | О(пријава) | О(1) |
Шта је Хеап?
Хрпа је структура података заснована на стаблу која формира комплетно бинарно стабло и задовољава својство хрпе. Ако је А родитељски чвор Б, онда је А уређено у односу на чвор Б за све чворове А и Б у гомили. То значи да вредност родитељског чвора може бити већа или једнака вредности подређеног чвора, или вредност родитељског чвора може бити мања или једнака вредности подређеног чвора. Дакле, можемо рећи да постоје две врсте гомила:
Обе гомиле су бинарна гомила, пошто свака има тачно два подређена чвора.
Операције приоритетног реда
Уобичајене операције које можемо да извршимо на приоритетном реду су уметање, брисање и завиривање. Хајде да видимо како можемо да одржавамо структуру података гомиле.
Ако убацимо елемент у приоритетни ред, он ће се померити на празан слот гледајући одозго према доле и са лева на десно.
стринг.валуеоф јава
Ако елемент није на исправном месту онда се упоређује са родитељским чвором; ако се утврди да није у реду, елементи се замењују. Овај процес се наставља све док се елемент не постави у исправан положај.
Као што знамо да је у максималној хрпи, максимални елемент основни чвор. Када уклонимо основни чвор, он ствара празан слот. Последњи уметнути елемент биће додат у овај празан слот. Затим се овај елемент пореди са подређеним чворовима, тј. левим дететом и десним дететом, и замењује се мањим од та два. Наставља се померати низ стабло све док се својство гомиле не обнови.
Апликације приоритетног реда
Следеће су апликације приоритетног реда:
- Користи се у Дијкстрином алгоритму најкраћег пута.
- Користи се у Примовом алгоритму
- Користи се у техникама компресије података као што је Хафманов код.
- Користи се у сортирању гомиле.
- Такође се користи у оперативном систему као што је распоређивање приоритета, балансирање оптерећења и руковање прекидима.
Програм за креирање приоритетног реда користећи бинарну максималну хрпу.
#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 > 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])>