우선순위 큐는 우선순위가 가장 높은 데이터를 가장 먼저 삭제하는 자료구조다.
우선순위 큐는 데이터를 우선순위에 따라 처리하고 싶을 때 사용한다.
우선순위 큐를 이해하기 위해서는 스택(Stack)과 큐(Queue) 자료구조의 개념을 아는 것이 필요하다.
먼저 스택(Stack)은 FILO(First_In,Last_Out)의 데이터 관리 방식을 따른다. 상자에 책을 쌓아두고 꺼낼 때 맨 위에 있는 책이 먼저 나오는 것과 같이 가장 나중에 삽입된 데이터가 먼저 추출되는 구조이다.
큐(Queue)는 FIFO(First_In,First_Out)의 구조로 스택과는 차이가 있다. 이는 가장 먼저 입력한 데이터를 가장 먼저 출력하는 구조이다. 은행에서 먼저 온 손님이 늦게 온 손님보다 먼저 서비스를 받게하기 위해 번호표를 나누어 주는 체계가 큐의 예시로 볼 수 있다.
우선순위 큐(Priority)는 FIFO,FILO가 아닌 가장 우선순위가 높은 데이터 먼저 추출하는 구조이다.
데이터를 우선순위에 따라 처리하고 싶을 때 사용하며, 예시로 상자에 물건을 쌓아두고 가치가 높은 물건을 꺼내서 확인해야하는 경우에 우선순위 큐의 방식으로 추출할 수 있다.
우선순위 큐를 만드는 방법은 두 가지가 있다.
1. 리스트를 사용한다.
2. heapq를 사용한다.
리스트와 힙의 시간 복잡도는 다음과 같다.
그림 출처 https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html
힙은 이진 힙이라고도 하며, 최솟값 및 최댓값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전 이진 트리를 기본으로 한 자료구조이다.
여기성 완전 이진 트리란 루트(root)노드부터 시작하여 왼쪽 자식노드, 오른쪽 자식노드 순서로 균형을 이루며 데이터가 차례대로 삽입되는 트리를 의미한다.
힙에는 두 가지 종류(최소 힙,최대 힙)가 있다.
-최소 힙(Min heap)
- 루트 노드가 가장 작은 값을 가진다.
- 따라서 값이 작은 데이터가 우선적으로 제거된다.
최소 힙은 루트 노드가 가장 작은 값을 가지려는 성질 때문에, 새로운 원소가 삽입 되었을 때(자식 노드가 추가 되었을 때) 최소 힙의 성질을 유지하기 위해 부모 노드와 비교하여 작으면 상단으로 올라가는 구조로 짜여져 있어 시간 복잡도가 일정하다.
다음은 위 과정을 그림으로 나타낸 것이다.
다음은 힙의 데이터 제거 과정이다.
그림 출처 https://www.youtube.com/watch?v=AjFlp951nz0&t=197s
-최대 힙(Max heap)
- 루트 노드가 가장 큰 값을 가진다.
- 따라서 값이 큰 데이터가 우선적으로 제거된다.
최대 힙은 최소 힙과 반대이다.
프로그래밍 언어마다 기본적으로 제공하는 heap 라이브러리는 다른데, 파이썬의 경우 기본적으로 힙 자료구조는 최소 힙 구조로 동작한다. 최대 힙 구조가 필요한 경우, 최소 힙의 입력과 추출에 마이너스(-)부호를 붙여 최대 힙을 구현할 수 있다.
