우선순위 큐
우선순위가 높은 것을 먼저 꺼내기 위하여 만들어진 자료구조이며, 힙(Heap)이라고도 부른다.
자바에는 자료구조 heap을 구현한 우선순위 큐 클래스가 있다.
큐를 생각해보면 가장 먼저 들어온 요소가 가장 먼저 나가게 되는데, 우선순위 큐에서는 요소들이
우선순위를 가져서 들어온 순서와 상관없이 우선순위가 높은 요소가 큐에서 가장 먼저 나가게 된다.
이때 나오는 요소는 우선순위가 가장 높은 heap 자료구조의 최상단 root node이다.
heap 자료구조는 가장 적은 값이나 가장 큰 값을 항상 최상단 root node에 위치시켜 이 값을 내보내는 자료구조이다.
우선순위가 가장 적은 값을 root node로 두면 최소 힙, 우선순위가 가장 높은 값을 root node로 두면 최대 힙이다.
- 중복값을 허용한다.
- 완전이진트리이다.
우선순위 큐의 시간 복잡도
우선순위 큐에서의 시간 복잡도는 삽입, 삭제 시 O(logN)의 시간이 걸린다.
삽입시 가장 마지막 위치에 요소를 추가시킨 후 부모 노드와의 비교 후 Swap 과정을 통해 알맞은 위치를 찾아간다.
upHeap
삭제 시 root node를 반환 후 가장 마지막 요소를 root node에 위치시킨 후 자손과의 비교를 통해 Swap 과정을 거쳐
알맞은 위치를 찾아간다.
자손과의 Swap은 둘 중 우선순위가 큰 node와 Swap한다.
downHeap
큐와 비슷한 성질을 이용하지만, 큐에서는 front 요소의 반환 시간은 O(1)이다. 하지만 우선순위 큐에서는 가장 우선순위가
높은 값을 가져온 후 완전 이진트리로 다시 만드는 과정인 Swap 과정 때문에 O(logN)이 걸린다.
Ref. https://komas.tistory.com/48
Ref. https://yoongrammer.tistory.com/81
