[자료구조] 우선순위 큐

우선순위 큐(Priority Queue)

• 평범한 큐나 스택과 비슷한 축약 자료형이나 각 원소들은 우선순위를 갖고 있음
• 높은 우선순위를 가진 원소는 낮은 우선순위를 가진 원소보다 먼저 처리됨
• 만약 두 원소가 같은 우선순위를 가진다면 그들은 큐에서 그들의 순서에 의해 처리됨
• 운영체제의 작업 스케줄링, 정렬, 네트워크 관리 등에 적용

 

우선순위 큐 vs. 큐

우선순위 큐	큐
트리구조.  최대 힙*을 이용해 구현함	선형적인 형태

*최대힙(Max Heap) : 부모노드가 자식노드 보다 값이큰 완전 이진 트리. 전체에서 루트 노드가 가장 값이 큼

 

 

우선순위 큐 삽입

O(logN)의 시간 복잡도를 가짐

1. 완전 이진 트리를 유지하는 형태로 순차적으로 삽입
2. 삽입 이후 루트 노드까지 거슬러 올라가면서 상향식으로 최대 힙을 구성함 

우선순위 큐 삭제

1. 루트 노드를 삭제하고 가장 마지막 원소를 루트 노드 위치로 옮김
2. 리프 노드까지 내려가면서 하향식으로 최대힙을 구성함

※ 부모의 인덱스는 자식 인덱스에서 1을 빼고 2로 나눈 값과 같음

 

 

 

 

참고 | Wikipedia, Fast campus 컴퓨터 공학 전공 필수