A prioritási sor egy absztrakt adattípus, amely a normál sorhoz hasonlóan viselkedik, azzal a különbséggel, hogy minden elemnek van bizonyos prioritása, azaz a legmagasabb prioritású elem lenne az első a prioritási sorban. A prioritási sor elemeinek prioritása határozza meg, hogy milyen sorrendben kerülnek eltávolításra az elemek a prioritási sorból.
A prioritási sor csak összehasonlítható elemeket támogat, ami azt jelenti, hogy az elemek növekvő vagy csökkenő sorrendben vannak elrendezve.
napfényes deol kor
Például tegyük fel, hogy van néhány értékünk, például 1, 3, 4, 8, 14, 22, beszúrva egy prioritási sorba, és az értékek sorrendje a legkisebbtől a legnagyobbig terjed. Ezért az 1-es számnak lesz a legmagasabb, míg a 22-nek a legalacsonyabb prioritása.
A prioritási sor jellemzői
A prioritási sor egy sor kiterjesztése, amely a következő jellemzőket tartalmazza:
- A prioritási sor minden eleméhez tartozik valamilyen prioritás.
- A magasabb prioritású elem a kisebb prioritású törlése előtt törlődik.
- Ha egy prioritási sorban két elemnek azonos a prioritása, akkor a FIFO-elv szerint lesznek elrendezve.
Értsük meg a prioritási sort egy példán keresztül.
Van egy prioritási sorunk, amely a következő értékeket tartalmazza:
1, 3, 4, 8, 14, 22
Az összes érték növekvő sorrendben van elrendezve. Most meg fogjuk figyelni, hogyan fog kinézni a prioritási sor a következő műveletek végrehajtása után:
A prioritási sor típusai
Kétféle prioritási sor létezik:
A prioritási sor ábrázolása
Most meglátjuk, hogyan ábrázolhatjuk a prioritási sort egy egyirányú listán keresztül.
A prioritási sort az alábbi lista segítségével hozzuk létre, amelyben INFO a lista tartalmazza az adatelemeket, PRN lista tartalmazza az egyes adatelemek prioritási számát a INFO listát, a LINK pedig alapvetően a következő csomópont címét tartalmazza.
Lépésről lépésre hozzuk létre a prioritási sort.
java sort arraylist
Prioritásos sor esetén az alacsonyabb prioritású szám a magasabb prioritású, azaz alacsonyabb prioritású szám = magasabb prioritás.
1. lépés: A listában az alacsonyabb prioritású szám 1, aminek az adatértéke 333, így az alábbi ábrán látható módon kerül be a listába:
2. lépés: A 333 beillesztése után a 2-es prioritás magasabb prioritású, és az ehhez a prioritáshoz tartozó adatértékek 222 és 111. Tehát ezek az adatok a FIFO elven alapulnak; ezért először 222, majd 111 kerül hozzáadásra.
3. lépés: A 2-es prioritás elemeinek beillesztése után a következő magasabb prioritási szám 4, a 4 prioritási számokhoz tartozó adatelemek pedig 444, 555, 777. Ebben az esetben az elemek beillesztése a FIFO elv alapján történik; ezért először 444, majd 555, majd 777 kerül hozzáadásra.
4. lépés: A 4-es prioritás elemeinek beillesztése után a következő magasabb prioritásszám 5, az 5-ös prioritáshoz tartozó érték pedig 666, tehát a sor végére kerül be.
A Priority Queue megvalósítása
A prioritási sor négyféleképpen valósítható meg, beleértve a tömböket, a linkelt listát, a kupac adatstruktúrát és a bináris keresési fát. A kupac adatstruktúra a prioritási sor megvalósításának leghatékonyabb módja, ezért ebben a témában a prioritási sort egy kupac adatszerkezettel fogjuk megvalósítani. Most először megértjük, miért a kupac a leghatékonyabb módja az összes többi adatstruktúra közül.
Bonyolultságok elemzése különböző implementációk segítségével
| Végrehajtás | add hozzá | Távolítsa el | kandikál |
| Linkelt lista | O(1) | Tovább) | Tovább) |
| Bináris kupac | O(bejelentkezés) | O(bejelentkezés) | O(1) |
| Bináris keresőfa | O(bejelentkezés) | O(bejelentkezés) | O(1) |
Mi az a Heap?
A kupac egy fa alapú adatstruktúra, amely teljes bináris fát alkot, és kielégíti a kupac tulajdonságot. Ha A B szülőcsomópontja, akkor A egy halomban lévő összes A és B csomópont B csomópontjához képest rendezett. Ez azt jelenti, hogy a szülőcsomópont értéke lehet nagyobb vagy egyenlő a gyermekcsomópont értékével, vagy a szülőcsomópont értéke kisebb vagy egyenlő lehet a gyermekcsomópont értékével. Ezért azt mondhatjuk, hogy kétféle kupac létezik:
Mindkét kupac bináris kupac, mivel mindegyiknek pontosan két gyermekcsomópontja van.
Prioritási sorműveletek
Az általános műveletek, amelyeket egy prioritási soron végezhetünk, a beillesztés, a törlés és a betekintés. Nézzük meg, hogyan tudjuk fenntartani a kupac adatstruktúrát.
Ha beszúrunk egy elemet egy prioritási sorba, akkor felülről lefelé és balról jobbra nézve az üres helyre kerül.
ingyenes vs ingyenes
Ha az elem nem a megfelelő helyen van, akkor a rendszer összehasonlítja a szülő csomóponttal; ha kiderül, hogy nincs rendben, akkor az elemek felcserélődnek. Ez a folyamat addig folytatódik, amíg az elem a megfelelő pozícióba nem kerül.
Mint tudjuk, hogy egy max kupacban a maximális elem a gyökércsomópont. Amikor eltávolítjuk a gyökércsomópontot, üres helyet hoz létre. Az utoljára beillesztett elem hozzáadódik ehhez az üres helyhez. Ezután ezt az elemet összehasonlítja a gyermek csomópontokkal, azaz a bal-gyermek és a jobb gyermek csomópontokkal, és felcseréli a kettő közül a kisebbel. Folyamatosan mozog lefelé a fán, amíg a kupactulajdon helyre nem kerül.
A prioritási sor alkalmazásai
A prioritási sor alkalmazásai a következők:
- A Dijkstra legrövidebb út algoritmusában használatos.
- A prim-algoritmusban használatos
- Az adattömörítési technikákban, például a Huffman-kódban használják.
- Halom rendezésben használják.
- Olyan operációs rendszerekben is használatos, mint a prioritás-ütemezés, a terheléselosztás és a megszakításkezelés.
Program a prioritási sor létrehozásához a bináris max kupac használatával.
#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])>