Priority Queue (우선순위 큐)

 

개념

- 큐의 스케줄링 방법 중 하나

- 각 원소들이 우선순위를 가지고 높은 우선순위를 가진 원소가 낮은 우선순위를 가진 원소보다 먼저 처리

- 원소가 같은 우선순위를 가지고 있다면 큐에 의해 먼저 삽입된 순서대로 처리되는 자료구조

- 배열, 리스트, 힙트리를 이용해서 구현할 수 있음

​

*배열, 리스트, 힙트리로 구현 시

- 배열로 구현할 경우 데이터 삽입 및 삭제 과정에서 비효율적

- 리스트로 구현할 경우 첫번째 노드와 마지막 노드까지 저장된 데이터와 우선순위 비교를 해야함

- 배열과 리스트는 정렬을 위해 요소 하나를 추가할 떄마다 이분검색 등을 이용해서 삽입될 위치를 찾아야함

- 힙트리의 구조를 이용하면 효과적으로 구현할 수 있음

(힙트리는 최소,최대값 기준으로 정렬되고 모든 내부 노드는 자신의 부모노드와의 관계만 신경쓰고 다른 노드들은 신경쓰지 않아도 됨)

(힙트리가 왜 효과적인지 알려면 트리 구조에 대해서 먼저 알아야 한다.)

​

*사용하는 이유

데이터 처리를 하는데 우선순위에 따라 처리가 되어야할 경우가 있다.

예를들어 디펜스 게임을 하는데 타워가 공격할 적을 판단할 때 일정 범위 안으로 들어온 적을 먼저 공격하도록 하는 구현을 한다고 하면 우선순위에 따라 구현할 수 있다.

AStar 길찾기 알고리즘에서도 우선순위 큐를 사용한다.

그 밖에 우선순위 큐를 이용하는것들이 있다는데 조금 더 알아보고 정리를 하도록 하겠다..

​

참고자료

5. 우선순위 큐와 힙(Prior Queue & Heap)

힙정렬과 우선순위큐

[정렬] 힙 정렬 (우선순위 큐)

우선 순위 큐(Priority Queue, Heap)

[자료구조] 우선순위 큐(Priority Queue) : BASIC

NoonGam's IT 블로그

07_어뎁터 컨테이너(스택, 큐, 우선순위 큐)

 

 

 

다람쥐와 포동포동이