[자료구조] 우선순위 큐(Priority Queue) & 힙(Heap)

1. 우선순위 큐(Priority Queue) 

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

우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용합니다. 

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

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

# 우선순위 큐를 구현하는 방법은 다양하다.

1) 단순히 리스트를 이용해서 구현할 수 있다.

2) 힙(Heap)을 이용해서 구현할 수 있다. 

 

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

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

-> 단순히 N개의 데이터를 힙에 넣었다가 모두 꺼내는 작업은 정렬과 동일하다. (힙 정렬) 

: 이 경우 시간복잡도는 O(NlogN)이다.

 

2. 힙(Heap) 

힙은 완전 이진 트리 자료구조의 일종이다. 

힙에서는 항상 루트 노드를 제거한다. 

- 최소 힙(min heap)

: 루트 노드가 가장 작은 값을 가진다. 따라서 값이 작은 데이터가 우선적으로 제거된다.

-최대 힙(max heap)

: 루트 노드가 가장 큰 값을 가진다. 따라서 값이 큰 데이터가 우선적으로 제거된다. 

 

최소힙과 최대힙

 

 

#참고

https://www.youtube.com/@dongbinna