priority queue data structure c with illustration
그림과 함께 C ++의 우선 순위 대기열 소개.
Priority Queue는 지난 자습서에서 논의한 대기열의 확장입니다.
특정 측면에서 대기열과 유사하지만 다음과 같은 점에서 일반 대기열과 다릅니다.
- 우선 순위 대기열의 각 항목은 우선 순위와 연결됩니다.
- 우선 순위가 가장 높은 항목이 대기열에서 제거되는 첫 번째 항목입니다.
- 둘 이상의 항목이 동일한 우선 순위를 갖는 경우 대기열에서의 순서가 고려됩니다.
=> Absolute C ++ 교육 시리즈를 보려면 여기를 클릭하십시오.
항목이 대기열에서 제거 될 때 우선 순위가 가장 높은 항목이 먼저 검색된다는 점을 제외하면 우선 순위 대기열을 대기열의 수정 된 버전으로 시각화 할 수 있습니다. 따라서 우선 순위에 따라 항목을 처리해야 할 때 대기열 대신 우선 순위 대기열을 사용하는 것을 선호합니다.
학습 내용 :
기본 작동
우선 순위 대기열에서 지원하는 몇 가지 기본 작업에 대해 설명하겠습니다.
- 삽입 (항목, 우선 순위) : 주어진 우선 순위로 우선 순위 큐에 항목을 삽입합니다.
- getHighestPriority () : 우선 순위가 가장 높은 항목을 반환합니다.
- deleteHighestPriority () : 우선 순위가 가장 높은 항목을 제거합니다.
위의 작업 외에도 isEmpty (), isFull () 및 peek ()와 같은 일반 대기열 작업을 사용할 수도 있습니다.
삽화
우선 순위 대기열의 그림을 보겠습니다. 단순화를 위해 우선 순위 대기열의 항목으로 ASCII 문자를 사용합니다. ASCII 값이 높을수록 우선 순위가 높습니다.
초기 상태 – 우선 순위 대기열 (PQ) – {} => 비어 있음
위의 그림에서 삽입 작업이 일반 대기열과 유사 함을 알 수 있습니다. 그러나 우선 순위 큐에 대해 'deleteHighestPriority'를 호출하면 우선 순위가 가장 높은 요소가 먼저 제거됩니다.
따라서이 함수를 처음 호출 할 때 항목 O가 제거되고 두 번째로 항목 M은 G 및 A보다 우선 순위가 높기 때문에 제거됩니다.
C ++에서 우선 순위 대기열 구현
우선 순위 대기열은 다음을 사용하여 구현할 수 있습니다.
# 1) 배열 / 연결된 목록
배열을 사용하여 우선 순위 대기열을 구현할 수 있으며 이것은 우선 순위 대기열에 대한 가장 간단한 구현입니다.
우선 순위 큐의 항목을 나타 내기 위해 다음과 같이 구조체를 선언하면됩니다.
struct pq_item{ int item; int priority; };우리는 각 항목에 대해서도 우선 순위를 선언했습니다.
우선 순위 대기열에 새 항목을 삽입하려면 배열 끝에 항목을 삽입하면됩니다.
getHighestPriority ()를 사용하여 큐에서 요소를 가져 오려면 처음부터 배열을 순회하고 우선 순위가 가장 높은 항목을 반환해야합니다.
마찬가지로 deleteHighestPriority 작업을 사용하여 대기열에서 항목을 제거하려면 전체 배열을 순회하고 우선 순위가 가장 높은 항목을 삭제해야합니다. 그런 다음 삭제 된 항목 뒤의 다른 모든 요소를 한 위치 뒤로 이동합니다.
연결 목록을 사용하여 우선 순위 대기열을 구현할 수도 있습니다. 배열과 비슷한 방식으로 모든 작업을 수행 할 수 있습니다. 유일한 차이점은 deleteHighestPriority를 호출 한 후 요소를 이동할 필요가 없다는 것입니다.
# 2) 힙
힙을 사용하여 우선 순위 대기열을 구현하는 것이 가장 효율적인 방법이며 연결된 목록 및 배열과 비교할 때 훨씬 더 나은 성능을 제공합니다. 연결된 목록 및 배열과 달리 힙 구현은 우선 순위 큐의 삽입 및 삭제 작업에 O (로그온) 시간이 걸립니다. 작업 가져 오기, getHighestPriority는 O (1) 시간이 걸립니다.
# 3) C ++의 표준 템플릿 라이브러리 (STL)에 내장 된 우선 순위 대기열
C ++에서는 가장 높은 요소가 큐의 첫 번째 요소이고 모든 요소가 내림차순이되도록 설계된 컨테이너 적응 형 클래스로서 우선 순위 큐가 있습니다.
따라서 우선 순위 대기열의 각 항목은 고정 된 우선 순위를 갖습니다.
우선 순위 큐 구현을 포함하는 STL에 클래스가 있습니다.
우선 순위 대기열에서 지원하는 다양한 작업은 다음과 같습니다.
- priority_queue :: size () : 큐의 크기를 반환합니다.
- priority_queue :: empty () : 큐가 비어 있는지 확인하고 상태를 반환합니다.
- priority_queue :: top () : 우선 순위 대기열의 최상위 요소에 대한 참조를 반환합니다.
- priority_queue :: push () : 우선 순위 대기열 끝에 항목을 추가합니다.
- priority_queue :: pop () : 우선 순위 큐에서 첫 번째 요소를 제거합니다.
- priority_queue :: 스왑 () : 한 우선 순위 대기열의 내용을 동일한 유형 및 크기의 다른 대기열로 교체하는 데 사용됩니다.
- 우선 순위 대기열 값 유형 : 값 유형은 우선 순위 대기열에 저장된 요소의 유형을 제공합니다. 이것은 템플릿 매개 변수의 동의어 역할도합니다.
- priority_queue :: emplace () : 대기열 맨 위에있는 우선 순위 대기열 컨테이너에 새 요소를 삽입하는 데 사용됩니다.
다음 프로그램에서는 C ++의 STL에있는 우선 순위 큐의 기능을 살펴 보겠습니다.
#include #include using namespace std; void displaypq(priority_queue pq) { priority_queue pqueue = pq; while (!pqueue.empty()) { cout << ' ' << pqueue.top(); pqueue.pop(); } cout << '
'; } int main () { priority_queue pq; pq.push(1); pq.push(3); pq.push(5); pq.push(7); pq.push(9); cout << 'Size of the queue(pq.size()): ' << pq.size(); cout << '
Top element of the queue(pq.top()): ' << pq.top(); cout << '
The priority queue pq is : '; displaypq(pq); cout << '
Priority queue, after pq.pop() operation : '; pq.pop(); displaypq(pq); return 0; } 산출:
soapui 인터뷰 질문 및 답변 doc
큐 크기 (pq.size ()) : 5
대기열의 최상위 요소 (pq.top ()) : 9
우선 순위 대기열 pq는 다음과 같습니다. 9 7 5 3 1
pq.pop () 작업 후 우선 순위 대기열 : 7 5 3 1
우선 순위 대기열을위한 Java 구현
Java의 Priority 대기열은 대기열의 모든 요소가 대기열과 함께 제공되는 비교기를 사용하여 자연 순서 또는 사용자 정의 순서에 따라 정렬되는 특수 대기열입니다.
Java의 우선 순위 대기열은 다음과 같습니다.
Java 우선 순위 큐에서 요소는 최소 요소가 큐의 앞쪽에 있고 가장 큰 요소가 큐의 뒤쪽에 있도록 배열됩니다. 따라서 우선 순위 대기열에서 요소를 제거하면 항상 제거되는 가장 작은 요소입니다.
Java에서 우선 순위 큐를 구현하는 클래스는 'PriorityQueue'이며 Java 콜렉션 프레임 워크의 일부입니다. Java의 'Queue'인터페이스를 구현합니다.
다음은 Java PriorityQueue 클래스의 클래스 계층 구조입니다.
다음은 Java의 항목으로 정수를 사용하는 우선 순위 대기열 기능의 예입니다.
import java.util.*; class Main { public static void main(String args()) { // Create empty priority queue PriorityQueue priority_Queue = new PriorityQueue(); // Adding items to the priority_Queue using add() priority_Queue.add(1); priority_Queue.add(3); priority_Queue.add(5); priority_Queue.add(7); // display the most priority element System.out.println('peek()::Head value:' + priority_Queue.peek()); // Print all elements in Priotity queue System.out.println('The priority queue:'); Iterator itr = priority_Queue.iterator(); while (itr.hasNext()) System.out.print(itr.next() + ' '); // poll() function to remove the queue elements priority_Queue.poll(); System.out.println('
After poll() function, priority queue:'); Iterator itr2 = priority_Queue.iterator(); while (itr2.hasNext()) System.out.print(itr2.next() + ' '); // remove() function with priority queue priority_Queue.remove(5); System.out.println('
After Remove(5) function, priority queue:'); Iterator itr3 = priority_Queue.iterator(); while (itr3.hasNext()) System.out.print(itr3.next() + ' '); // Check if an element is present using contains() boolean b = priority_Queue.contains(3); System.out.println ( '
Priority queue contains 3?: ' + b); // use toArray() function to get objects from the queue and display the array elements Object() arr = priority_Queue.toArray(); System.out.println ( 'Array elements: '); for (int i = 0; i 산출:
peek () :: 헤드 값 : 1
우선 순위 대기열 :
1 3 5 7
poll () 함수 후 우선 순위 큐 :
3 7 5
Remove (5) 함수 후 우선 순위 대기열 :
3 7
우선 순위 대기열에 3 개 포함? : true
배열 요소 :
값 : 3
값 : 7
위 프로그램에서 Java의 PriorityQueue 클래스를 사용하여 Integer 객체를 포함하는 PriorityQueue 객체를 생성합니다. 'add'기능을 사용하여 큐에 요소를 추가합니다. 그런 다음 poll () 함수가 호출되고 최소 요소 인 큐의 앞쪽에서 요소를 삭제합니다.
다시 대기열에서 매개 변수로 지정된 요소를 제거하는 'remove ()'함수를 호출합니다. 또한 'Contains ()'함수를 사용하여 특정 요소가 대기열에 있는지 확인합니다. 마지막으로 'toArray ()'함수를 사용하여 대기열을 배열 객체로 변환합니다.
신청
- 운영 체제 부하 분산 및 인터럽트 처리기 : 로드 밸런싱 및 인터럽트 처리와 같은 운영 체제 기능은 우선 순위 대기열을 사용하여 구현됩니다. 부하 분산 활동은 부하 분산을 효과적으로 수행하기 위해 가장 높은 우선 순위로 리소스를 예약합니다. 인터럽트 처리는 우선 순위가 가장 높은 인터럽트를 서비스하여 수행됩니다. 이 기능은 우선 순위 대기열을 사용하여 효과적으로 구현할 수 있습니다.
- 라우팅 : 라우팅은 최소 처리 시간으로 최대 처리량을 얻을 수 있도록 네트워크 리소스를 라우팅하는 데 사용되는 기능입니다. 우선 순위 대기열을 사용하여 구현할 수도 있습니다.
- 병원 응급 : 병원 응급실에서는 환자의 상태가 얼마나 심각한 지에 따라 환자를 진료합니다. 우선 순위 대기열을 사용하여 시뮬레이션 할 수 있습니다.
- Dijkstra의 최단 경로 알고리즘 : 여기서 그래프는 인접 목록으로 저장되며 우선 순위 대기열을 사용하여 인접 목록에서 최소 가중치 에지를 효율적으로 추출하여 Dijkstra의 최단 경로 알고리즘을 구현할 수 있습니다.
- 우선 순위 대기열은 스패닝 트리를 구현하는 동안 노드 키를 저장하고 최소 키 노드를 추출하는 데 사용할 수도 있습니다.
결론
우선 순위 대기열은 대기열의 확장 일뿐입니다. 그러나 FIFO 방식을 사용하여 항목을 추가 / 제거하는 대기열과 달리 우선 순위 대기열에서는 우선 순위에 따라 항목이 대기열에서 제거됩니다. 따라서 대기열의 각 항목은 우선 순위와 연관되며 우선 순위가 가장 높은 항목이 대기열에서 가장 먼저 제거됩니다.
우선 순위 큐에는 insert (), getHighestPriority () 및 deleteHighestPriority ()의 세 가지 주요 작업이 있습니다. 우선 순위 대기열은 배열 또는 연결 목록을 사용하여 구현할 수 있지만 작업은 그다지 효율적이지 않습니다. 우선 순위 대기열은 힙을 사용하여 구현할 수도 있으며 성능이 훨씬 빠릅니다.
C ++에는 우선 순위 대기열의 기능을 구현하는 컨테이너 클래스도 있습니다. Java에는 우선 순위 대기열의 기능을 제공하는 내장 클래스 priority_queue가 있습니다.
우선 순위 대기열은 주로 우선 순위에 따라 항목을 처리해야하는 응용 프로그램에서 사용됩니다. 예를 들어, 인터럽트 처리에 사용됩니다.
다가오는 튜토리얼은 큐의 또 다른 확장 인 순환 큐에 대한 모든 것을 탐구 할 것입니다.
=> 전문가의 전체 C ++ 과정을 보려면 여기를 방문하십시오.
추천 도서