[자료구조] Priority Queue / 우선순위 큐

• Priority Queue 우선순위 큐 #자료구조

설명 :

Priority Queue는 말 그대로 우선순위 큐로써, 일반적인 선입선출과는 다른 개념이다.

우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조이다.

우선순위 큐는 데이터를 우선순위에 따라, 처리하고 싶을 때 사용하는 자료구조

 

예시) 물건 데이터를 자료구조에 넣었다가, 가치가 높은 물건부터 꺼내서 확인해야 하는 경우

자료구조	추출되는 데이터
스택	가장 나중에 삽입된 데이터
큐	가장 먼저 삽입된 데이터
우선순위 큐	가장 우선순위가 높은 데이터

 

 

그런데 그 우선순위를 어떻게 정함?...누구 맘대로...

 

구현 방법 :

첫번째 방법. 단순하게 리스트를 이용하여 구현 가능

두번째 방법. 힙을 이용하여 구현 가능

 

- 데이터 개수가 N개일 때, 구현 방식에 따라서 시간 복잡도를 비교한 내용은 아래와 같음

우선순위 큐 구현방식	삽입 시간	삭제 시간
리스트	O(1)	O(N)
힙(heap)	O(logN)	O(logN)

 

우선순위 큐 구현방식 中 단순하게 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 '힙 정렬'과 동일하지만, 이 경우 시간 복잡도는 O(NlogN)이다...

 

 

-힙(Heap)의 특징

image - 완전 이진 트리

힙 : 완전 이진 트리 자료구조의 일종

힙에서는 항상 루트 노드(뿌리 노드)를 삭제함

 

제거방식에는 두 가지가 있는데 최소 힙 / 최대 힙

 

 

 

 

 

최소 힙 : 루트 노드가 가장 작은 값을 가짐, 그래서 값이 가장 작은 데이터가 1등으로 우선적으로 제거됨

최대 힙 : 루트 노드가 가장 큰 값을 가짐, 그래서 값이 큰 데이터가 우선적으로 제거