Priority Queue (우선순위 큐)

사실 글의 주제와 크게 연관있는 사진 같진 않은데 그냥 사진 한 장도 안 넣으니까 허전해서 하나 넣어봤다. 출처: https://prepinsta.com/c-program/priority-queue-using-arrays/

Priority Queue (우선순위 큐)?

 - 우선순위를 가지고 있는 큐

 - 우선순위에 따라서 처리된다. (Not FIFO)

 - 우선순위 큐가 힙인 것이 아니라 우선순위 큐를 구현하는 것 중 대표적이고 효율적인 방법이 힙인 것 

 - 노드 하나의 추가/삭제가 시간 복잡도가 O(logN)이고 최대값/최소값을 O(1)에 구할 수 있다. 

 - 완전 정렬보다 관리 비용이 적다. 

 - 배열을 통해 트리 형태를 쉽게 구현할 수 있다. 

 - 부모나 자식 노드를 O(1)연산으로 쉽게 찾을 수 있다.

 - n위치에 있는 노드의 자식은 2^n과 2^(n+1) 사이에 위치한다.

 - 완전 이진 트리의 특성에 의해 삽입/삭제의 위치는 자료의 시작과 끝 인덱스로 쉽게 판단할 수 있다.

 

힙 정렬

 힙 정렬은 힙 자료구조를 이용해서 이진트리와 유사한 방법으로 수행된다. 

 정렬 단계

1. 하나의 값을 힙에 삽입한다(반복).
2. 힙에서 순차적(오름차순)으로 값을 하나씩 제거한다. 

 

힙 정렬의 시간 복잡도

 - N개의 노드 삽입 연산 + N개의 노드 삭제 연산 

 - 노드 하나의 삽입과 삭제 연산은 각각 O(logN)이다. 

 - N개의 원소를 가지는 힙의 전체 정렬은 O(NlongN)이다.

 

자바에서 우선순위 큐의 사용

 * java.util.PriorityQueue

 - heap 자료구조

 - 최대 heap (가장 큰 값을 기준으로 큰 순서대로 나옴)

 - 최소 heap (가장 작은 값을 기준으로 작은 순서대로 나옴)

 - 원소들끼리 비교해야 하니까 반드시 모든 원소는 Comparable 인터페이스를 구현해야 함

 

* java.util.PriorityQueue(Comparator comparator)

 - 명시된 Comparator의 구현에 따라 원소들의 순서를 유지한다.

 

 

참고 - https://www.programiz.com/dsa/priority-queue