Heap의 원리를 응용한 PriorityQueue에 대해 알아봅시다.
PriorityQueue에서 Queue를 보고 "그 FIFO(First In First Out)의 큐랑 비슷한건가?" 라고
생각하시기 쉬운데 아닙니다.
PQ 는 우선순위를 먼저 결정하고 우선순위가 높은 엘리먼트가 먼저 나가는 자료구조입니다.
데이터를 삽입할 때 우선순위를 기준으로 최대힙 혹은 최소 힙을 구성하고
데이터를 꺼낼 때 루트 노드를 얻어낸 뒤 루트 노드를 삭제할 때는 빈 루트 노드 위치에 맨 마지막 노드를 삽입한 후 아래로 내려가면서 적절한 자리를 찾아서 옮기는 방식으로 진행됩니다.
말로만 설명하니 무슨소리인가 싶으니 그림을 가져오겠습니다.
예시로, PQ로 된, [2,3,5,7,9,10] 이 있다고 가정하고 생성하겠습니다.
보이시는것 같이 완전이진트리로 구성되어있습니다.
PQ의 내부구조는 Heap으로 이루워져있기 때문입니다!
그렇다면 PQ가 데이터 삽입할(add,offer)때 무슨 원리로 작동할까?
1.우선 들어온 데이터를 마지막자리에 넣습니다.
2. 들어온 데이터를 부모와 비교합니다.
if(부모>데이터면) 서로 자리를 바꿉니다.
더이상 바꿀경우가없으면 종료합니다.
반면에 PQ가 데이터 제거할때(poll,remove) 무슨 원리로 작동할까?
1. 부모노드와 맨 마지막 노드의 위치를 바꿉니다. 그리고, 마지막노드를 제거합니다.(2 제거)
2. 자식들과 비교해서, 작은값과 비교해서 자리를 바꿉니다.(우선순위 낮은순대로라면)
더이상 바꿀 경우가 없으면 종료합니다.
삽입과 제거연산을 보셧을때, PQ는 매번 모든원소를 정렬하지않습니다.
매번 원소를 뽑거나 추가할때, 그 원소의 자리만 정렬합니다.
따라서, PQ에다가 숫자를 넣은뒤, 하나씩 하나씩 뽑아서 출력하면,
일반적인 삽입정렬O(n^2) 배열보다 적은 연산O(nlogn)을 하는 특징을가집니다.
'알고리즘 > 알고리즘 지식' 카테고리의 다른 글
| 재귀함수와 스택 (자료구조)의 작동원리 (0) | 2021.08.11 |
|---|