728x90
우선순위 큐란, 기존 큐 방식인 FIFO 방식과 함께 우선순위를 정하여 해당 방향으로 정렬을 하는 큐라고 생각하시면 됩니다. 우선순위를 어떻게 지정하냐에 따라서 큐가 바뀝니다.
우선순위 큐는 대부분은 힙을 이용하여 구현합니다.
힙은 완전이진 트리 형태의 자료구조입니다.
여러 개의 값 중 최댓값 또는 최솟값을 찾아내는 연산이 빠르다는 장점이 있습니다.
그리고 이진 탐색 트리(BST)와 달리 중복 값을 허용합니다.
힙의 종류는 2가지 정도가 있는 데, 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있습니다.
이 둘을 판단하는 기준은 아주 단순합니다.
부모 노드 ≥ 자식 노드 (즉, 부모 노드의 key 값이 자식 노드보다 크거나 같은 완전 이진트리) 라면, 최대 힙입니다.
그 반대라면 최소 힙입니다.
부모 노드 ≤ 자식 노드 (즉, 부모 노드의 key 값이 자식 노드보다 작거나 같은 완전 이진트리)
위에 설명드렸듯이 우선순위 큐는 반드시 힙을 이용을 하지 않아도 된다고 하였습니다.
(대부분 우선순위 큐를 사용할 때에는 힙을 이용하기 때문에 우선순위 큐의 특징 = 힙의 특징이라고 오해하시는 분들이 있어서 설명해드립니다. 배열 또는 연결 리스트를 사용하여 구현할 수도 있습니다.)
이상입니다.
'공부 > 알고리즘, 자료구조' 카테고리의 다른 글
| [프로그래머스] 주식가격 (0) | 2022.02.17 |
|---|---|
| [프로그래머스] 다리를 지나는 트럭 (0) | 2022.02.16 |
| [프로그래머스] 프린터 (0) | 2022.02.15 |
| [프로그래머스] 기능개발 (0) | 2022.02.14 |
| [프로그래머스] K번째 수 (0) | 2022.02.12 |