A prioritārā rinda ir rindas veids, kas sakārto elementus, pamatojoties uz to prioritārajām vērtībām. Elementi ar augstākām prioritātes vērtībām parasti tiek izgūti pirms elementiem ar zemākām prioritātes vērtībām.

Prioritātes rindā katram elementam ir ar to saistīta prioritātes vērtība. Kad rindai pievienojat elementu, tas tiek ievietots pozīcijā, pamatojoties uz tā prioritātes vērtību. Piemēram, ja prioritārajai rindai pievienojat elementu ar augstu prioritātes vērtību, tas var tikt ievietots rindas priekšpusē, savukārt elements ar zemu prioritātes vērtību var tikt ievietots aizmugurē.

Ir vairāki veidi, kā ieviest prioritāro rindu, tostarp izmantojot masīvu, saistīto sarakstu, kaudzi vai bināro meklēšanas koku. Katrai metodei ir savas priekšrocības un trūkumi, un labākā izvēle būs atkarīga no jūsu lietojumprogrammas īpašajām vajadzībām.

Prioritātes rindas bieži tiek izmantotas reāllaika sistēmās, kur elementu apstrādes secībai var būt būtiskas sekas. Tos izmanto arī algoritmos, lai uzlabotu to efektivitāti, piemēram, Dijkstras algoritms īsākā ceļa atrašanai grafikā un A* meklēšanas algoritmu ceļa atrašanai.

Prioritātes rindas īpašības

Tātad prioritārā rinda ir paplašinājums rindā ar šādām īpašībām.

• Katram vienumam ir ar to saistīta prioritāte.
• Elements ar augstu prioritāti tiek izslēgts no rindas pirms elementa ar zemu prioritāti.
• Ja diviem elementiem ir vienāda prioritāte, tie tiek apkalpoti atbilstoši to secībai rindā.

Tālāk norādītajā prioritātes rindā elementam ar maksimālo ASCII vērtību būs augstākā prioritāte. Vispirms tiek pasniegti elementi ar augstāku prioritāti.

Kā prioritārās rindas elementiem tiek piešķirta prioritāte?

Prioritātes rindā parasti prioritātes piešķiršanai tiek ņemta vērā elementa vērtība.

Piemēram, elementam ar augstāko vērtību tiek piešķirta augstākā prioritāte, bet elementam ar zemāko vērtību tiek piešķirta zemākā prioritāte. Var izmantot arī apgriezto gadījumu, t.i., elementam ar zemāko vērtību var piešķirt augstāko prioritāti. Arī prioritāti var piešķirt atbilstoši mūsu vajadzībām.

Prioritārās rindas darbības:

Tipiska prioritātes rinda atbalsta šādas darbības:

1) ievietošana prioritārajā rindā

Kad prioritārajā rindā tiek ievietots jauns elements, tas tiek pārvietots uz tukšo slotu no augšas uz leju un no kreisās uz labo pusi. Tomēr, ja elements nav pareizajā vietā, tas tiks salīdzināts ar vecākmezglu. Ja elements nav pareizā secībā, elementi tiek apmainīti. Apmaiņas process turpinās, līdz visi elementi ir novietoti pareizajā pozīcijā.

2) Dzēšana prioritārajā rindā

Kā jūs zināt, ka maksimālajā kaudzē maksimālais elements ir saknes mezgls. Un tas noņems elementu, kuram vispirms ir maksimālā prioritāte. Tādējādi jūs noņemat saknes mezglu no rindas. Šī noņemšana izveido tukšu slotu, kas tiks aizpildīta ar jaunu ievietošanu. Pēc tam tas salīdzina tikko ievietoto elementu ar visiem rindā esošajiem elementiem, lai saglabātu kaudzes invariantu.

3) Ielūkojieties prioritārajā rindā

Šī darbība palīdz atgriezt maksimālo elementu no Max Heap vai minimālo elementu no Min Heap, neizdzēšot mezglu no prioritārās rindas.

Prioritāro rindu veidi:

1) Prioritātes rinda augošā secībā

Kā norāda nosaukums, augošā secībā prioritātes rindā elementam ar zemāku prioritātes vērtību prioritāšu sarakstā tiek piešķirta augstāka prioritāte. Piemēram, ja mums ir šādi elementi prioritārā rindā, kas sakārtoti augošā secībā, piemēram, 4,6,8,9,10. Šeit 4 ir mazākais skaitlis, tāpēc tam tiks piešķirta augstākā prioritāte prioritārajā rindā, un tāpēc, kad mēs noņemam rindu no šāda veida prioritārās rindas, 4 noņems no rindas un rindā atgriež 4.

2) Prioritātes rinda dilstošā secībā

Kā jūs, iespējams, zināt, saknes mezgls ir maksimālais elements maksimālajā kaudzē. Tas arī vispirms noņems elementu ar augstāko prioritāti. Tā rezultātā saknes mezgls tiek noņemts no rindas. Šī dzēšana atstāj tukšu vietu, kas turpmāk tiks aizpildīta ar jauniem ievietojumiem. Pēc tam kaudzes invariants tiek uzturēts, salīdzinot tikko ievietoto elementu ar visiem citiem ierakstiem rindā.

Prioritāro rindu veidi

Atšķirība starp prioritāro rindu un parasto rindu?

Elementiem rindā nav pievienota prioritāte, tiek ieviests FIFO noteikums, savukārt prioritārā rindā elementiem ir prioritāte. Vispirms tiek pasniegti elementi ar augstāku prioritāti.

Kā ieviest prioritāro rindu?

Prioritātes rindu var ieviest, izmantojot šādas datu struktūras:

kas ir Linux failu sistēma

• Masīvi
• Saistītais saraksts
• Kaudzes datu struktūra
• Binārais meklēšanas koks

Apspriedīsim visu to sīkāk.

1) Ieviesiet prioritāro rindu, izmantojot masīvu:

Vienkārša ieviešana ir šādas struktūras masīva izmantošana.

struct item {
int vienums;
int priority;
}

enqueue(): šo funkciju izmanto, lai rindā ievietotu jaunus datus. dequeue(): šī funkcija no rindas noņem elementu ar augstāko prioritāti. peek()/top(): šī funkcija tiek izmantota, lai rindā iegūtu visaugstākās prioritātes elementu, nenoņemot to no rindas.

C++

>

>

Java

>

>

Python3

jvm java

>

>

C#

>

>

Javascript

>

>

16 14 12>

Piezīme: Lasīt Šis raksts lai iegūtu sīkāku informāciju.

2) Ieviesiet prioritāro rindu, izmantojot saistīto sarakstu:

LinkedList ieviešanā ieraksti tiek sakārtoti dilstošā secībā, pamatojoties uz to prioritāti. Augstākās prioritātes elements vienmēr tiek pievienots prioritātes rindas priekšpusē, kas tiek veidota, izmantojot saistītos sarakstus. Funkcijas, piemēram push () , pop () , un palūrēt () tiek izmantoti, lai ieviestu prioritāro rindu, izmantojot saistītu sarakstu, un ir izskaidroti šādi:

push(): šo funkciju izmanto, lai rindā ievietotu jaunus datus. pop(): šī funkcija no rindas noņem elementu ar augstāko prioritāti. peek() / top(): šī funkcija tiek izmantota, lai rindā iegūtu visaugstākās prioritātes elementu, nenoņemot to no rindas.

C++

kartes atkārtošana java

>

>

Java

> 
    
   
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 # Python3 code to implement Priority Queue> # using Singly Linked List> # Class to create new node which includes> # Node Data, and Node Priority> class> PriorityQueueNode:> >def> _init_(>self>, value, pr):> >self>.data>=> value> >self>.priority>=> pr> >self>.>next> => None> # Implementation of Priority Queue> class> PriorityQueue:> >def> _init_(>self>):> >self>.front>=> None> ># Method to check Priority Queue is Empty> ># or not if Empty then it will return True> ># Otherwise False> >def> isEmpty(>self>):> >return> True> if> self>.front>=>=> None> else> False> ># Method to add items in Priority Queue> ># According to their priority value> >def> push(>self>, value, priority):> ># Condition check for checking Priority> ># Queue is empty or not> >if> self>.isEmpty()>=>=> True>:> ># Creating a new node and assigning> ># it to class variable> >self>.front>=> PriorityQueueNode(value,> >priority)> ># Returning 1 for successful execution> >return> 1> >else>:> ># Special condition check to see that> ># first node priority value> >if> self>.front.priority   # Creating a new node  newNode = PriorityQueueNode(value,  priority)  # Updating the new node next value  newNode.next = self.front  # Assigning it to self.front  self.front = newNode  # Returning 1 for successful execution  return 1  else:  # Traversing through Queue until it  # finds the next smaller priority node  temp = self.front  while temp.next:  # If same priority node found then current  # node will come after previous node  if priority>= temp.next.priority: break temp = temp.next newNode = PriorityQueueNode(vērtība, prioritāte) newNode.next = temp.next temp.next = newNode # Atgriež 1 veiksmīgai izpildei return 1 # Augstas prioritātes vienuma # noņemšanas metode no Priority Queue def pop(self): # Pārbaudes stāvokļa pārbaude # Prioritātes rinda ir tukša vai nav, ja self.isEmpty() == True: return else: # Augstas prioritātes mezgla noņemšana no # Prioritātes rindas un priekšējā # atjaunināšana ar nākamo node self.front = self.front.next return 1 # Augstas prioritātes mezgla atgriešanas metode # vērtība Nenoņem def peek(self): # Pārbaudes stāvokļa pārbaude Prioritāte # Rinda ir tukša vai nav, ja self.isEmpty() == True: return else: return self.front.data # Metode, lai izietu cauri prioritātei # Rindas def traverse(self): # Pārbaudes stāvokļa pārbaude Prioritāte # Rinda ir tukša vai nav, ja self.isEmpty() == True: return ' Rinda ir tukša!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # Draivera kods if _name_ == '_main_': # Izveidojot prioritātes # rindas gadījums un vērtību pievienošana # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # Pārvietošanās caur prioritāro rindu pq.traverse() # Augstākās prioritātes vienuma # noņemšana prioritārajai rindai pq.pop()>
 
 
 
 
    
 
>
 
    
 
>
 
 
C#
    
 
     
  
 
    
 
     
     
    
 
 
 
 
 
 // C# code to implement Priority Queue> // using Linked List> using> System;> class> GFG> {> >// Node> >public> class> Node> >{> >public> int> data;> >// Lower values indicate> >// higher priority> >public> int> priority;> >public> Node next;> >}> >public> static> Node node =>new> Node();> >// Function to Create A New Node> >public> static> Node newNode(>int> d,>int> p)> >{> >Node temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> >}> >// Return the value at head> >public> static> int> peek(Node head)> >{> >return> (head).data;> >}> >// Removes the element with the> >// highest priority from the list> >public> static> Node pop(Node head)> >{> >Node temp = head;> >(head) = (head).next;> >return> head;> >}> >// Function to push according to priority> >public> static> Node push(Node head,> >int> d,>int> p)> >{> >Node start = (head);> >// Create new Node> >Node temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> ((head).priority   {   // Insert New Node before head   temp.next = head;   (head) = temp;   }   else  {   // Traverse the list and find a   // position to insert new node   while (start.next != null &&   start.next.priority>p) {sākt = start.next;   } // Vai nu saraksta beigās // vai vajadzīgajā pozīcijā temp.next = start.next;   start.next = temp;   } atgriešanās galva;   } // Funkcija, lai pārbaudītu, vai saraksts ir tukšs public static int isEmpty(Node head) { return ((head) == null) ? 1:0;   } // Draivera kods public static void Main(string[] args) { // Izveidot prioritāro rindu // 7.4.5.6 Node pq = newNode(4, 1);   pq = push(pq, 5, 2);   pq = push(pq, 6, 3);   pq = push(pq, 7, 0);   while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq));   pq = pop(pq);   } } } // Šo kodu nodrošina ishankhandelwals.>>
 
 
 
 
    
 
> 
    
   
 
     
  
 
    
 
     
     
    
python rstrip
 
 
 
 
 
 // JavaScript code to implement Priority Queue> // using Linked List> // Node> class Node {> >// Lower values indicate> >// higher priority> >constructor() {> >this>.data = 0;> >this>.priority = 0;> >this>.next =>null>;> >}> }> var> node =>new> Node();> // Function to Create A New Node> function> newNode(d, p) {> >var> temp =>new> Node();> >temp.data = d;> >temp.priority = p;> >temp.next =>null>;> >return> temp;> }> // Return the value at head> function> peek(head) {> >return> head.data;> }> // Removes the element with the> // highest priority from the list> function> pop(head) {> >var> temp = head;> >head = head.next;> >return> head;> }> // Function to push according to priority> function> push(head, d, p) {> >var> start = head;> >// Create new Node> >var> temp = newNode(d, p);> >// Special Case: The head of list> >// has lesser priority than new node.> >// So insert new node before head node> >// and change head node.> >if> (head.priority   // Insert New Node before head  temp.next = head;  head = temp;  }  else {  // Traverse the list and find a  // position to insert new node  while (start.next != null && start.next.priority>p) {sākt = start.next;  } // Vai nu saraksta beigās // vai vajadzīgajā pozīcijā temp.next = start.next;  start.next = temp;  } atgriešanās galva; } // Pārbaudāmā funkcija ir tukša funkcija isEmpty(head) { return head == null ? 1:0; } // Draivera kods // Prioritātes rindas izveide // 7.4.5.6 var pq = newNode(4, 1); pq = push(pq, 5, 2); pq = push(pq, 6, 3); pq = push(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' ');  pq = pop(pq); } // Šo kodu nodrošina ishankhandelwals.>>
 
 
 
 
    
 
> 
    
  6 5 4 7>
 
Plašāku informāciju skatiet šajā rakstā.
  
 
  Piezīme: Mēs varam arī izmantot Saistīto sarakstu, visu darbību laika sarežģītība ar saistīto sarakstu paliek tāda pati kā masīvam. Saistītā saraksta priekšrocība ir   dzēstAugstākā prioritāte()   var būt efektīvāki, jo mums nav jāpārvieto priekšmeti.
 
 
  3) Ieviesiet prioritāro rindu, izmantojot kaudzes:  
 
Binārā kaudze parasti tiek dota priekšroka prioritāro rindu ieviešanai, jo kaudzes nodrošina labāku veiktspēju salīdzinājumā ar masīviem vai LinkedList. Ņemot vērā kaudzes īpašības, ieraksts ar lielāko taustiņu atrodas augšpusē un to var nekavējoties noņemt. Tomēr atlikušo atslēgu kaudzes rekvizīta atjaunošanai būs nepieciešams laiks O(log n). Tomēr, ja nekavējoties jāievieto cits ieraksts, daļu no šī laika var apvienot ar O(log n) laiku, kas nepieciešams jaunā ieraksta ievietošanai. Tādējādi prioritārās rindas kā kaudzes attēlošana izrādās izdevīga lielam n, jo tā tiek efektīvi attēlota blakus esošajā krātuvē un tiek garantēta, ka gan ievietošanai, gan dzēšanai ir nepieciešams tikai logaritmisks laiks. Darbības ar bināro kaudzi ir šādas:
 
insert(p): ievieto jaunu elementu ar prioritāti p. extractMax(): izvelk elementu ar maksimālu prioritāti. remove(i): noņem elementu, uz kuru norāda iterators i. getMax(): atgriež elementu ar maksimālu prioritāti. changePriority(i, p): maina tā elementa prioritāti, uz kuru norāda i uz lpp .
 
 
 
 
Binārā kaudze
 
 
 
ievietot ()
 
 
 
noņemt ()
 
 
 
palūrēt ()
 
 
 
 
 
 
Laika sarežģītība
 
 
 
O(log n)
 
 
 
O(log n)
 
 
 
O(1)
 
 
 
 
  
 
Informāciju par koda ieviešanu skatiet šajā rakstā.
 
 
  4) Ieviesiet prioritāro rindu, izmantojot bināro meklēšanas koku:  
 
Lai ieviestu prioritāro rindu, var izmantot arī pašbalansējošu bināro meklēšanas koku, piemēram, AVL koku, sarkanmelnu koku utt. Tādas darbības kā peek(), insert() un delete() var veikt, izmantojot BST.
 
 
 
Binārais meklēšanas koks
 
palūrēt ()
 
ievietot ()
 
dzēst()
 
 
 
 
Laika sarežģītība
 
O(1)
 
O(log n)
 
O(log n)
 
 
 
 
  Prioritātes rindas lietojumprogrammas:  
 
 
CPU plānošana
 
Grafiku algoritmi, piemēram, Dijkstra īsākā ceļa algoritms, Prim minimālais aptverošais koks utt.
 
Stack ieviešana
 
Visas prioritātes rindas lietojumprogrammas
 
  Prioritātes rinda programmā C++  
 
Prioritātes rinda Java
 
  Prioritātes rinda Python  
 
Prioritātes rinda JavaScript
 
Jaunākie raksti par prioritāro rindu!