우선순위 대기열이란 무엇입니까 | 우선순위 대기열 소개 - TECHCODEVIEW.COM

ㅏ 우선순위 대기열 우선 순위 값에 따라 요소를 정렬하는 대기열 유형입니다. 우선순위 값이 높은 요소는 일반적으로 우선순위 값이 낮은 요소보다 먼저 검색됩니다.

우선순위 대기열에서 각 요소에는 관련된 우선순위 값이 있습니다. 대기열에 요소를 추가하면 해당 요소는 우선순위 값에 따라 위치에 삽입됩니다. 예를 들어, 우선순위 값이 높은 요소를 우선순위 큐에 추가하면 해당 요소는 큐의 앞쪽에 삽입되고, 우선순위 값이 낮은 요소는 뒤쪽에 삽입될 수 있습니다.

배열, 연결된 목록, 힙 또는 이진 검색 트리를 사용하는 것을 포함하여 우선순위 대기열을 구현하는 여러 가지 방법이 있습니다. 각 방법에는 고유한 장점과 단점이 있으며, 최선의 선택은 애플리케이션의 특정 요구 사항에 따라 달라집니다.

우선순위 큐는 요소가 처리되는 순서가 중요한 결과를 가져올 수 있는 실시간 시스템에서 자주 사용됩니다. 또한 다음과 같은 효율성을 향상시키기 위해 알고리즘에 사용됩니다. Dijkstra의 알고리즘 그래프에서 최단 경로를 찾는 방법과 경로 찾기를 위한 A* 검색 알고리즘이 있습니다.

우선순위 대기열의 속성

따라서 우선순위 큐는 우선순위 큐의 확장입니다. 대기줄 다음과 같은 속성을 가지고 있습니다.

모든 항목에는 해당 항목과 관련된 우선순위가 있습니다.
우선순위가 높은 요소는 우선순위가 낮은 요소보다 먼저 대기열에서 제거됩니다.
두 요소의 우선순위가 동일한 경우 대기열의 순서에 따라 처리됩니다.

아래 우선순위 큐에서는 최대 ASCII 값을 가진 요소가 가장 높은 우선순위를 갖습니다. 우선순위가 높은 요소가 먼저 제공됩니다.

우선순위 대기열의 요소에 우선순위는 어떻게 할당됩니까?

우선순위 큐에서는 일반적으로 우선순위를 할당하기 위해 요소의 값이 고려됩니다.

예를 들어, 가장 높은 값을 가진 요소에는 가장 높은 우선순위가 할당되고 가장 낮은 값을 가진 요소에는 가장 낮은 우선순위가 할당됩니다. 반대의 경우도 사용할 수 있습니다. 즉, 가장 낮은 값을 가진 요소에 가장 높은 우선순위가 할당될 수 있습니다. 또한 필요에 따라 우선순위를 지정할 수도 있습니다.

우선순위 대기열의 작동:

일반적인 우선순위 큐는 다음 작업을 지원합니다.

1) 우선순위 큐에 삽입

새 요소가 우선순위 큐에 삽입되면 위에서 아래로, 왼쪽에서 오른쪽으로 빈 슬롯으로 이동합니다. 그러나 요소가 올바른 위치에 있지 않으면 상위 노드와 비교됩니다. 요소의 순서가 올바르지 않으면 요소가 교체됩니다. 모든 요소가 올바른 위치에 배치될 때까지 교체 프로세스가 계속됩니다.

2) 우선순위 큐에서의 삭제

아시다시피 최대 힙에서 최대 요소는 루트 노드입니다. 그리고 우선순위가 가장 높은 요소를 먼저 제거합니다. 따라서 대기열에서 루트 노드를 제거합니다. 이렇게 제거하면 빈 슬롯이 생성되고, 이 슬롯은 새로운 삽입으로 채워집니다. 그런 다음 새로 삽입된 요소를 큐 내부의 모든 요소와 비교하여 힙 불변성을 유지합니다.

3) 우선순위 대기열 엿보기

이 작업은 우선순위 큐에서 노드를 삭제하지 않고도 최대 힙에서 최대 요소를 반환하거나 최소 힙에서 최소 요소를 반환하는 데 도움이 됩니다.

우선순위 대기열의 유형:

1) 오름차순 우선순위 대기열

이름에서 알 수 있듯이 오름차순 우선순위 큐에서는 우선순위 값이 낮은 요소에 우선순위 목록에서 더 높은 우선순위가 부여됩니다. 예를 들어, 4,6,8,9,10과 같이 오름차순으로 정렬된 우선순위 큐에 다음 요소가 있다고 가정합니다. 여기서 4는 가장 작은 숫자이므로 우선순위 큐에서 가장 높은 우선순위를 가지므로 이러한 유형의 우선순위 큐에서 큐를 빼면 4가 큐에서 제거되고 큐에서 빼면 4가 반환됩니다.

2) 내림차순 우선순위 큐

아시다시피 루트 노드는 최대 힙의 최대 요소입니다. 또한 우선순위가 가장 높은 요소를 먼저 제거합니다. 결과적으로 루트 노드가 대기열에서 제거됩니다. 이 삭제로 인해 빈 공간이 남게 되며 향후 새로운 삽입으로 채워질 것입니다. 그런 다음 새로 삽입된 요소를 대기열의 다른 모든 항목과 비교하여 힙 불변성이 유지됩니다.

우선순위 대기열의 유형

우선순위 큐와 일반 큐의 차이점은 무엇입니까?

큐의 요소에는 우선순위가 부여되지 않으며 FIFO(선입선출) 규칙이 구현되는 반면, 우선순위 큐에서는 요소에 우선순위가 있습니다. 우선순위가 높은 요소가 먼저 제공됩니다.

우선순위 대기열을 구현하는 방법은 무엇입니까?

우선순위 큐는 다음 데이터 구조를 사용하여 구현할 수 있습니다.

배열
연결리스트
힙 데이터 구조
이진 검색 트리

이 모든 것을 자세히 논의해 보겠습니다.

1) 배열을 사용하여 우선순위 대기열 구현:

간단한 구현은 다음 구조의 배열을 사용하는 것입니다.

구조체 항목 {
정수 항목;
정수 우선순위;
}

enqueue(): 이 함수는 대기열에 새로운 데이터를 삽입하는 데 사용됩니다. dequeue(): 이 함수는 대기열에서 우선순위가 가장 높은 요소를 제거합니다. peek()/top(): 이 함수는 대기열에서 요소를 제거하지 않고 대기열에서 우선순위가 가장 높은 요소를 가져오는 데 사용됩니다.

배열	대기열에 넣기()	따라서 ()	몰래 엿보다()
시간 복잡도	오(1)	에)	에)

C++

// C++ program to implement Priority Queue> // using Arrays> #include> using> namespace> std;> // Structure for the elements in the> // priority queue> struct> item {> >int> value;> >int> priority;> };> // Store the element of a priority queue> item pr[100000];> // Pointer to the last index> int> size = -1;> // Function to insert a new element> // into priority queue> void> enqueue(>int> value,>int> priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> int> peek()> {> >int> highestPriority = INT_MIN;> >int> ind = -1;> >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind; } // Function to remove the element with // the highest priority void dequeue() {  // Find the position of the element  // with highest priority  int ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--; } // Driver Code int main() {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);  // Stores the top element  // at the moment  int ind = peek();  cout << pr[ind].value << endl;  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  cout << pr[ind].value << endl;  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  cout << pr[ind].value << endl;  return 0; }>

자바

// Java program to implement Priority Queue> // using Arrays> import> java.util.*;> // Structure for the elements in the> // priority queue> class> item {> >public> int> value;> >public> int> priority;> };> class> GFG {> >// Store the element of a priority queue> >static> item[] pr =>new> item[>100000>];> >// Pointer to the last index> >static> int> size = ->1>;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority = Integer.MIN_VALUE;> >int> ind = ->1>;> >// Check for the element with> >// highest priority> >for> (>int> i =>0>; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority> >&& ind>->1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind;  }  // Function to remove the element with  // the highest priority  static void dequeue()  {  // Find the position of the element  // with highest priority  int ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--;  }  public static void main(String[] args)  {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);  // Stores the top element  // at the moment  int ind = peek();  System.out.println(pr[ind].value);  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  System.out.println(pr[ind].value);  // Dequeue the top element  dequeue();  // Check the top element  ind = peek();  System.out.println(pr[ind].value);  } } // this code is contributed by phasing17>

파이썬3

import> sys> # Structure for the elements in the> # priority queue> class> item :> >value>=> 0> >priority>=> 0> class> GFG :> > ># Store the element of a priority queue> >pr>=> [>None>]>*> (>100000>)> > ># Pointer to the last index> >size>=> ->1> > ># Function to insert a new element> ># into priority queue> >@staticmethod> >def> enqueue( value, priority) :> > ># Increase the size> >GFG.size>+>=> 1> > ># Insert the element> >GFG.pr[GFG.size]>=> item()> >GFG.pr[GFG.size].value>=> value> >GFG.pr[GFG.size].priority>=> priority> > ># Function to check the top element> >@staticmethod> >def> peek() :> >highestPriority>=> ->sys.maxsize> >ind>=> ->1> > ># Check for the element with> ># highest priority> >i>=> 0> >while> (i <>=> GFG.size) :> > ># If priority is same choose> ># the element with the> ># highest value> >if> (highestPriority>=>=> GFG.pr[i].priority>and> ind>>->1> and>

GFG.pr[ind].value   highestPriority = GFG.pr[i].priority  ind = i  elif(highestPriority   highestPriority = GFG.pr[i].priority  ind = i  i += 1    # Return position of the element  return ind    # Function to remove the element with  # the highest priority  @staticmethod  def dequeue() :    # Find the position of the element  # with highest priority  ind = GFG.peek()    # Shift the element one index before  # from the position of the element  # with highest priority is found  i = ind  while (i   GFG.pr[i] = GFG.pr[i + 1]  i += 1    # Decrease the size of the  # priority queue by one  GFG.size -= 1  @staticmethod  def main( args) :    # Function Call to insert elements  # as per the priority  GFG.enqueue(10, 2)  GFG.enqueue(14, 4)  GFG.enqueue(16, 4)  GFG.enqueue(12, 3)    # Stores the top element  # at the moment  ind = GFG.peek()  print(GFG.pr[ind].value)    # Dequeue the top element  GFG.dequeue()    # Check the top element  ind = GFG.peek()  print(GFG.pr[ind].value)    # Dequeue the top element  GFG.dequeue()    # Check the top element  ind = GFG.peek()  print(GFG.pr[ind].value)   if __name__=='__main__':  GFG.main([])    # This code is contributed by aadityaburujwale.>

씨#

bfs를 위한 뭔가

// C# program to implement Priority Queue> // using Arrays> using> System;> // Structure for the elements in the> // priority queue> public> class> item {> >public> int> value;> >public> int> priority;> };> public> class> GFG> {> > >// Store the element of a priority queue> >static> item[] pr =>new> item[100000];> >// Pointer to the last index> >static> int> size = -1;> >// Function to insert a new element> >// into priority queue> >static> void> enqueue(>int> value,>int> priority)> >{> >// Increase the size> >size++;> > >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> >}> > >// Function to check the top element> >static> int> peek()> >{> >int> highestPriority =>int>.MinValue;> >int> ind = -1;> > >// Check for the element with> >// highest priority> >for> (>int> i = 0; i <= size; i++) {> > >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }    // Return position of the element  return ind;  }    // Function to remove the element with  // the highest priority  static void dequeue()  {  // Find the position of the element  // with highest priority  int ind = peek();    // Shift the element one index before  // from the position of the element  // with highest priority is found  for (int i = ind; i   pr[i] = pr[i + 1];  }    // Decrease the size of the  // priority queue by one  size--;  }  public static void Main(string[] args)  {  // Function Call to insert elements  // as per the priority  enqueue(10, 2);  enqueue(14, 4);  enqueue(16, 4);  enqueue(12, 3);    // Stores the top element  // at the moment  int ind = peek();    Console.WriteLine(pr[ind].value);    // Dequeue the top element  dequeue();    // Check the top element  ind = peek();  Console.WriteLine(pr[ind].value);    // Dequeue the top element  dequeue();    // Check the top element  ind = peek();  Console.WriteLine(pr[ind].value);  } } //this code is contributed by phasing17>

자바스크립트

// JavaScript program to implement Priority Queue> // using Arrays> // Structure for the elements in the> // priority queue> class item {> >constructor()> >{> >this>.value;> >this>.priority;> >}> };> // Store the element of a priority queue> let pr = [];> for> (>var> i = 0; i <100000; i++)> >pr.push(>new> item());> // Pointer to the last index> let size = -1;> // Function to insert a new element> // into priority queue> function> enqueue(value, priority)> {> >// Increase the size> >size++;> >// Insert the element> >pr[size] =>new> item();> >pr[size].value = value;> >pr[size].priority = priority;> }> // Function to check the top element> function> peek()> {> >let highestPriority = Number.MIN_SAFE_INTEGER;> >let ind = -1;> >// Check for the element with> >// highest priority> >for> (>var> i = 0; i <= size; i++) {> >// If priority is same choose> >// the element with the> >// highest value> >if> (highestPriority == pr[i].priority && ind>-1> >

&& pr[ind].value   highestPriority = pr[i].priority;  ind = i;  }  else if (highestPriority   highestPriority = pr[i].priority;  ind = i;  }  }  // Return position of the element  return ind; } // Function to remove the element with // the highest priority function dequeue() {  // Find the position of the element  // with highest priority  let ind = peek();  // Shift the element one index before  // from the position of the element  // with highest priority is found  for (var i = ind; i   pr[i] = pr[i + 1];  }  // Decrease the size of the  // priority queue by one  size--; } // Function Call to insert elements // as per the priority enqueue(10, 2); enqueue(14, 4); enqueue(16, 4); enqueue(12, 3); // Stores the top element // at the moment let ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // Dequeue the top element dequeue(); // Check the top element ind = peek(); console.log(pr[ind].value); // this code is contributed by phasing17>

산출

16 14 12>

메모: 읽다 이 기사 상세 사항은.

2) 연결 목록을 사용하여 우선순위 대기열 구현:

LinkedList 구현에서는 항목이 우선순위에 따라 내림차순으로 정렬됩니다. 우선순위가 가장 높은 요소는 항상 연결 목록을 사용하여 구성된 우선순위 대기열 앞에 추가됩니다. 다음과 같은 기능 푸시() , 팝() , 그리고 몰래 엿보다() 연결리스트를 사용하여 우선순위 큐를 구현하는 데 사용되며 다음과 같이 설명됩니다.

push(): 이 함수는 대기열에 새로운 데이터를 삽입하는 데 사용됩니다. pop(): 이 함수는 대기열에서 우선순위가 가장 높은 요소를 제거합니다. peek() / top(): 이 함수는 대기열에서 요소를 제거하지 않고 대기열에서 우선순위가 가장 높은 요소를 가져오는 데 사용됩니다.

연결리스트	푸시()	팝()	몰래 엿보다()
시간 복잡도	에)	오(1)	오(1)

C++

// C++ code to implement Priority Queue> // using Linked List> #include> using> namespace> std;> // Node> typedef> struct> node {> >int> data;> >// Lower values indicate> >// higher priority> >int> priority;> >struct> node* next;> } Node;> // Function to create a new node> Node* newNode(>int> d,>int> p)> {> >Node* temp = (Node*)>malloc>(>sizeof>(Node));> >temp->데이터 = d;> >temp->우선순위 = p;> >temp->다음 = NULL;> >return> temp;> }> // Return the value at head> int> peek(Node** head) {>return> (*head)->데이터; }> // Removes the element with the> // highest priority form the list> void> pop(Node** head)> {> >Node* temp = *head;> >(*head) = (*head)->다음;> >free>(temp);> }> // Function to push according to priority> void> 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> >if>

((*head)->우선 순위 // 헤드 앞에 새 노드 삽입 temp->next = *head;  (*머리) = 온도;  } else { // 목록을 탐색하여 // 새 노드를 삽입할 위치를 찾습니다. while (start->next != NULL && start->next->priority> p) { start = start->next;  } // 목록의 끝에서 // 또는 필요한 위치에서 temp->next = start->next;  시작->다음 = 임시;  } } // 목록이 비어 있는지 확인하는 함수 int isEmpty(Node** head) { return (*head) == NULL; } // 드라이버 코드 int main() { // 우선순위 대기열 생성 // 7->4->5->6 Node* pq = newNode(4, 1);  push(&pq, 5, 2);  push(&pq, 6, 3);  push(&pq, 7, 0);  while (!isEmpty(&pq)) { cout<< ' ' << peek(&pq);  pop(&pq);  }  return 0; }>

자바

// Java code to implement Priority Queue> // using Linked List> import> java.util.* ;> class> Solution> {> // Node> static> class> Node {> >int> data;> > >// Lower values indicate higher priority> >int> priority;> >Node next;> > }> static> Node node =>new> Node();> > // Function to Create A New Node> 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> static> int> peek(Node head)> {> >return> (head).data;> }> > // Removes the element with the> // highest priority from the list> static> Node pop(Node head)> {> >Node temp = head;> >(head) = (head).next;> >return> head;> }> > // Function to push according to priority> 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) { 시작 = start.next;  } // 목록의 끝이나 // 필요한 위치에 temp.next = start.next;  start.next = 임시;  } 헤드를 반환합니다. } // 목록이 비어 있는지 확인하는 함수 static int isEmpty(Node head) { return ((head) == null)?1:0; } // 드라이버 코드 public static void main(String args[]) { // 우선순위 큐 생성 // 7.4.5.6 노드 pq = newNode(4, 1);  pq =push(pq, 5, 2);  pq =push(pq, 6, 3);  pq =push(pq, 7, 0);    while (isEmpty(pq)==0) { System.out.printf('%d ', peek(pq));  pq=팝(pq);  } } } // 이 코드는 ishankhandelwals가 제공한 것입니다.>

파이썬

# 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(value, Priority) newNode.next = temp.next temp.next = newNode # 성공적인 실행을 위해 1을 반환 return 1 # 높은 우선순위 항목을 제거하는 메서드 # 우선순위 큐 def pop(self): # 확인을 위한 조건 검사 # 우선순위 큐가 비어 있는지 여부 if self.isEmpty() == True: return else: # 우선순위 큐에서 우선순위가 높은 노드를 # 제거하고 # 다음으로 앞부분을 업데이트 node self.front = self.front.next return 1 # 높은 우선순위를 반환하는 메서드 node # value Not Removal it def peek(self): # 우선순위 확인을 위한 조건 확인 # 대기열이 비어 있는지 여부 if self.isEmpty() == True: return else: return self.front.data # 우선순위를 통과하는 방법 # 큐 def traverse(self): # 우선순위 확인을 위한 조건 확인 # 큐가 비어 있는지 여부 if self.isEmpty() == True: return ' 대기열이 비어 있습니다!' else: temp = self.front while temp: print(temp.data, end=' ') temp = temp.next # 드라이버 코드 if _name_ == '_main_': # 생성 우선순위 # 큐의 인스턴스 및 값 추가 # 7 -> 4 -> 5 -> 6 pq = PriorityQueue() pq.push(4, 1) pq.push(5, 2) pq.push(6, 3) pq .push(7, 0) # 우선순위 큐를 통과 pq.traverse() # 우선순위 큐에서 가장 높은 우선순위 항목 # 제거 pq.pop()>

씨#

// 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) { 시작 = start.next;   } // 목록의 끝이나 // 필요한 위치에 temp.next = start.next;   start.next = 임시;   } 헤드를 반환합니다.   } // 목록이 비어 있는지 확인하는 함수 public static int isEmpty(Node head) { return ((head) == null) ? 1:0;   } // 드라이버 코드 public static void Main(string[] args) { // 우선순위 큐 생성 // 7.4.5.6 노드 pq = newNode(4, 1);   pq = 푸시(pq, 5, 2);   pq = 푸시(pq, 6, 3);   pq = 푸시(pq, 7, 0);   while (isEmpty(pq) == 0) { Console.Write('{0:D} ', peek(pq));   pq = 팝(pq);   } } } // 이 코드는 ishankhandelwals가 제공한 것입니다.>

자바스크립트

// 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) { 시작 = start.next;  } // 목록의 끝이나 // 필요한 위치에 temp.next = start.next;  start.next = 임시;  } 헤드를 반환합니다. } // 목록이 비어 있는지 확인하는 함수 function isEmpty(head) { return head == null ? 1:0; } // 드라이버 코드 // 우선순위 대기열 생성 // 7.4.5.6 var pq = newNode(4, 1); pq = 푸시(pq, 5, 2); pq = 푸시(pq, 6, 3); pq = 푸시(pq, 7, 0); while (isEmpty(pq) == 0) { console.log(peek(pq),' ');  pq = 팝(pq); } // 이 코드는 ishankhandelwals가 제공한 것입니다.>

산출

 6 5 4 7>

자세한 내용은 이 문서를 참조하세요.

메모: Linked List를 사용할 수도 있습니다. Linked List를 사용한 모든 작업의 시간 복잡도는 배열과 동일하게 유지됩니다. 연결리스트의 장점은 deleteHighestPriority() 항목을 이동할 필요가 없으므로 더 효율적일 수 있습니다.

3) 힙을 사용하여 우선순위 대기열 구현:

힙은 배열이나 LinkedList에 비해 더 나은 성능을 제공하기 때문에 일반적으로 우선순위 대기열 구현에 바이너리 힙이 선호됩니다. 힙의 속성을 고려하면 가장 큰 키를 가진 항목이 맨 위에 위치하며 즉시 제거가 가능합니다. 그러나 나머지 키의 힙 속성을 복원하는 데는 O(log n) 시간이 걸립니다. 그러나 다른 항목을 즉시 삽입해야 하는 경우 이 시간 중 일부는 새 항목을 삽입하는 데 필요한 O(log n) 시간과 결합될 수 있습니다. 따라서 우선순위 큐를 힙으로 표현하는 것은 연속된 저장소에서 효율적으로 표현되고 삽입과 삭제 모두에 대수 시간만 필요하도록 보장되기 때문에 큰 n에 유리한 것으로 입증되었습니다. 바이너리 힙에서의 작업은 다음과 같습니다:

내가 p에게

바이너리 힙	끼워 넣다()	제거하다()	몰래 엿보다()
시간 복잡도	O(로그 n)	O(로그 n)	오(1)

코드 구현에 대해서는 이 문서를 참조하세요.

4) 이진 검색 트리를 사용하여 우선순위 대기열 구현:

AVL 트리, 레드-블랙 트리 등과 같은 자체 균형 이진 검색 트리를 사용하여 우선순위 대기열을 구현할 수도 있습니다. peek(), insert() 및 delete()와 같은 작업은 BST를 사용하여 수행할 수 있습니다.

이진 검색 트리	몰래 엿보다()	끼워 넣다()	삭제()
시간 복잡도	오(1)	O(로그 n)	O(로그 n)

우선순위 대기열의 응용:

CPU 스케줄링
Dijkstra의 최단 경로 알고리즘, Prim의 최소 스패닝 트리 등과 같은 그래프 알고리즘
스택 구현
우선순위 대기열의 모든 응용 프로그램
C++의 우선순위 큐
Java의 우선순위 대기열
Python의 우선순위 대기열
JavaScript의 우선순위 대기열
우선순위 대기열에 대한 최신 기사!