CS 자료구조 Priority Queue(우선순위 큐)

 

우선순위 큐는 일반적인 큐와 다르게 데이터를 우선순위에 따라 처리하는 자료구조다. 큐에 들어오는 데이터가 삽입된 순서가 아닌 각 데이터에 지정된 우선순위에 따라 먼저 처리된다.

 

ㅇ 우선순위 큐의 특징

• 우선순위에 따라 처리
  일반적인 큐에서는 선입선출(FIFO) 방식으로 데이터를 처리하지만, 우선순위 큐에서는 우선순위가 높은 데이터가 먼저 처리된다. 우선순위가 높은 데이터가 먼저 빠져나오고, 낮은 데이터는 나중에 처리된다.
• 우선순위의 종류
  
  최대 우선순위 큐(Max Priority Queue)
  가장 큰 우선순위를 가진 요소가 먼저 처리된다.
  
  최소 우선순위 큐(Min Priority Queue)
  가장 작은 우선순위를 가진 요소가 먼저 처리된다.
  
  
• 구현 방법
  우선순위 큐는 일반적으로 힙(Heap) 자료 구조를 사용하여 구현된다. 힙은 빠르게 최대(소)값을 추출할 수 있는 자료구조이기 때문에 우선순위 큐의 연산을 효율적으로 처리할 수 있다.
  
  최대 힙으로 최대 우선순위 큐 구현
  최소 힙으로 최소 우선순위 큐 구현

 

ㅇ 우선순위 큐의 주요 연산

삽입(Insertion)

• 우선순위 큐에 새로운 데이터를 삽입할 때, 그 데이터는 우선순위에 따라 적절한 위치에 배치된다.
• 힙을 사용하여 구현된 우선순위 큐에서는 새 데이터를 트리의 마지막 자리에 삽입한 후 상향조정을 통해 우선순위가 높은 데이터가 루트로 올라갈 수 있게한다.
• 시간복잡도: O(log n)

최대(소)값 추출(Extract Max/Min)

• 우선순위 큐에서 우선순위가 가장 높은 데이터를 추출한다.
• 루트에 있는 데이터가 추출되고 하향조정을 통해 힙 속성을 복원한다.
• 시간 복잡도: O(log n)

최대(소)값 조회(Peek Max/Min)

• 우선순위 큐에서 우선순위가 가장 높은 값을 조회한다.(루트 노드)
• 데이터를 삭제하지 않고 단순히 확인만하는 작업이다.
• 시간 복잡도: O(1)

 

ㅇ 우선순위 큐의 장단점

장점

• 우선순위가 높은 데이터를 빠르게 추출할 수 있다.
• 효율적인 시간 복잡도

단점

• 배열이나 리스트에 비해 구현이 더 복잡할 수 있다.
• 데이터 전체 순회가 필요한 경우 비효율적이다. 힙은 정렬된 자료구조가 아니기 때문

 

ㅇ 우선순위 큐의 구현방법

• 힙(가장 효율적으로 구현가능)
• 정렬된 배열 또는 리스트
• 정렬되지 않은 배열 또는 리스

 

ㅇ 우선순위 큐의 활용

• 운영체제
  CPU 스케줄링, 작업 스케줄링에서 높은 우선순위의 작업을 먼저 처리
• 네트워크 라우팅
  패킷 전송 시 긴급도에 따라 우선순위를 매겨 중요한 데이터를 먼저 전송할 때 사용
• 알고리즘
  그래프 탐색 알고리즘에서 최소 가중치 경로나 최소 신장 트리를 찾는데 유용