View
📌 우선순위 큐란?
FIFO 형식의 큐와 달리 들어오는 순서에 상관없이 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조이다.
우선순위 큐를 구현하는 방법
- 배열로 구현
- 연결리스트로 구현
- 힙(Heap)을 이용
1) 배열 및 연결리스트
배열이나 연결리스트를 이용해서 우선 순위 큐를 구현하는 경우 간단하게 구현이 가능하다는 장점이 있다.
하지만 배열의 경우에는 여러가지 단점이 존재한다.
- 데이터 삽입 및 삭제 과정에서 데이터를 한 칸씩 당기거나 밀어야하는 연산을 계속해야 한다.
- 삽입의 위치를 찾기 위해 배열에 저장된 모든 데이터와 우선순위를 비교해야 한다.
2) 힙
배열의 shift 연산, 연결리스트의 삭제 및 삽입 하는 경우 순회하는 시간복잡도에 비해 힙을 통한 삽입 삭제는 부모와 자식 간에만 비교 하기 때문에 시간 복잡도 O(NlogN) 으로 해결 할 수 있다.
힙의 특성상 부모와 자식의 간의 비교를 통해서 우선 순위를 나누고 힙 정렬을 통해 지속적으로 정리 해준다. 원소를 제거할 때는 가장 마지막 노드가 루트 노드의 위치에 오도록 한다.
1. 힙이란?
힙(Heap)이란 완전 이진트리 형태의 자료구조로 힙 조건을 만족한다. 일차원 배열로 구현할 수 있고 일반적으로 그룹을 정렬하거나 입력된 데이터 안에서 최소/최대 값을 찾을 때 사용한다. 데이터의 삽입과 삭제가 빠르며 각각의 수행시간이 O(logN)이다.
2. 최소 힙과 최대 힙
1) 최대 힙 (Max Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 크거나 같은 완전 이진 트리
2) 최소 힙 (Min Heap) : 부모 노드의 키 값이 자식 노드의 키 값보다 작거나 같은 완전 이진 트리
* 완전 이진트리 : 마지막 레벨을 제외하곤 완전히 꽉 찬 상태이고, 마지막 레벨의 맨 왼쪽부터 꽉 차 있어야함.
3. 힙의 구현
1) 힙의 삽입 연산
① 트리의 가장 마지막 위치에 노드를 삽입한다.
② 추가된 노드와 그 부모 노드가 힙 조건을 만족하는지 확인한다.
③ 만족하지 않는다면 부모와 자식의 키 값을 바꾼다.
④ 조건에 만족하거나 추가된 노드가 루트에 도달할 때 까지 2~3을 반복한다.
2) 힙의 삭제 연산
① 힙의 삭제 연산은 항상 루트 노드를 삭제한다.
② 트리의 가장 마지막 노드를 루트 자리로 삽입한다.
③ 바꾼 위치의 노드가 힙 조건을 만족하는지 확인한다.
④ 만족하지 않는다면 왼쪽 자식과 오른쪽 자식 중 적합한 노드와 키 값을 바꾼다.
⑤ 조건을 만족하거나 리프 노드에 도달할 때 까지 3~4를 반복한다.
📃 우선순위 큐 사용법
- 선언
// 낮은 숫자가 우선 순위인 int 형 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();
// 높은 숫자가 우선 순위인 int 형 우선순위 큐
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(Collections.reverseOrder());
만약 따로 우선순위 옵션을 주고 싶다면 Compartor을 통해서 구현하면된다.
- 삽입
priorityQueue.add(1); //삽입에 성공하면 true를 반환하고, 실패한다면 IllegalStateException를 반환
priorityQueue.offer(2);
우선순위 큐에 값을 삽입하면, 그와 동시에 내부 힙을 통해서 부모와 자식간의 값을 비교해서 우선순위가 높은 순으로 정렬한다.
- 삭제
// 큐에서 우선순위에 따라 정렬된 값중 가장 첫번째 값을 반환함과 동시에 큐에서 제거한다.
// 만약 큐가 비어있다면 null을 반환한다.
priorityQueue.poll();
// 큐에서 가장 첫번째 값을 제거한다.
priorityQueue.remove();
// 큐를 비운다.
priorityQueue.clear();
- 출력
priorityQueue.peek();
[참고]
'알고리즘' 카테고리의 다른 글
[알고리즘] 06-3. 특수 정렬 알고리즘(기수/계수) (0) | 2022.12.20 |
---|---|
[알고리즘] Scanner VS BufferedReader (0) | 2022.11.28 |
스택(Stack) (0) | 2022.10.13 |