자료구조 - 우선순위 큐

다익스트라 사용할 때 그냥 큐에서 직접조회 방식으로 우선순위가 높은( 그리디 방법 으로 볼 수도 있다 ) 

가격이 싼 노드를 찾아와서 문제를 해결했었는데 간단하게 우선순위 큐를 사용하면 문제를 더 쉽게 해결 할 수있다.

물론 시간적으로 우선순위 큐가 더 안좋다는 이슈를 얼핏 들은 것같기도 하지만 가지고 있는 라이브러리를 최대한 이용하는 게 중요하다고 생각한다.

 

우선 순위 큐란?

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

데이터를 우선순위에 따라 처리하고 싶을 때 사용한다. 대표적으로 나누어서 보자

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

pop을 가치가 높은 순서부터 뽑고 싶을 때 사용하게 된다.

우선순위 큐 구현 방식 시간복잡도는 다음과 같다

우선순위 큐 구현 방식	삽입 시간	삭제 시간
리스트	O(1) 뒤에만 추가	O(N) 일일이 조회
힙(Heap)	O(logN)	O(logN)

결국 전체 조회 삭제는 O(NlogN) 이 된다.

힙이란?

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

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

최소 힙(min heap)	루트 노드가 가장 작은 값을 가진다. 값이 작은 데이터가 우선적으로 제거된다.
최대 힙(max heap)	루트 노드가 가장 큰 값을 가진다. 값이 큰 데이터가 우선적으로 제거된다.

힙을 어떻게 구성하게 되는가?

heapify() 라는 함수를 사용하여 구성한다.

heapify에는 2가지 종류가 있으며 각각 상향식, 하향식이다. (자식에서 부모로 대조 or 부모에서 자식으로 대조)

heapify를 사용해서 임의의 리스트를 정렬 할 수도 있다. => 해당 부분은 heap을 처음부터 구성하므로 build heap이라고도 한다.

(NlogN의 시간복잡도)

 

원소의 삽입의 경우 이미 완성된 heap에 대해서 진행되므로 해당 노드에 대해서만 heapify를 진행한다. 방식은 상향식이다.

원소의 삭제의 경우 이미 완성된 heap에 대해서 진행되는데, 삭제할 노드(pop) 와 마지막 노드의 위치를 변경한 뒤에 하향식으로 heapify를 진행한다.

 

그래서 파이썬에서는 뭘 써야해?

간단하다. 파이썬에서는 우선순위 큐를 사용하고 싶다면 heapq를 사용하면 된다.

물론 Priority Queue 라이브러리도 존재한다.

둘간의 차이는 그저 PriorityQueue는 Thread-Safe하고 heapq는 Non-safe이다.

어차피 코테에서는 멀티스레드 환경도 아니고하니 heapq를 사용하는 것이 맞다.

 

그냥 import heapq사용하면 된다.