[자료구조] 우선순위 큐 (Priority Queue)
우선순위 큐
우선순위 큐란?
- 큐의 종류이다. 하지만 모든 items 들이 우선순위를 가지는 자료구조 이다.
- 높은 우선순위를 가진 item 들이 먼저 나온다.
- 우선순위에 의해 sorted 된 경우
- Delete 는 fast. 하지만 Insert 이슈가 있습니다.
- Insert 는 fast. 하지만 Delete 이슈가 있습니다.
Binary Tree Implementation
AVL 2-3, 2-3-4 Tree 혹은 Red-Black Tree 구조를 사용할 수 있습니다. (not BST)
트리의 최하단 leaf 까지 왼쪽으로만 내려가면 원하는 값을 얻을 수 있습니다.
즉, 시간복잡도 O(logN) 을 가지며 Insert 와 Delete 를 할 수 있습니다.
하지만, 더 빠르고, 간단한 implementation 이 가능합니다. AVL 트리구조에서도 우선순위 큐를 구현할 수 있지만,
단순히 큰 우선순위 item을 Delete 하기에는 AVL 트리 구조는 너무 무겁습니다.
=======
하지만, 더 빠르고, 간단한 implementation 이 가능합니다. AVL 트리구조에서도 우선순위 큐를 구현할 수 있지만, 단순히 큰 우선순위 item을 Delete 하기에는 AVL 트리 구조는 너무 무겁습니다.
이에 대안으로 Heap Structure 가 있습니다.
여전히 시간복잡도 O(logN) 을 갖지만 몇배 빠른 성능을 가집니다.
Heap
definition
- 노드들의 모양은 Complete Binary Tree 입니다.
- 마지막 level 을 제외하고 모든 level 은 full 상태를 가집니다.
- 마지막 level 은 왼쪽부터 채워집니다.
- 부모는 자식보다 작은 key 를 가집니다.
- 하지만, 왼쪽 오른쪽 자식들끼리는 order 가 없습니다.
implications
- Root 에는 가장 작은 값을 가집니다.
- 어느 방향으로든, 내려갈수록 큰 key 를 얻습니다.
Array Representation
- 루트의 인덱스는 1 입니다.
- 노트의 왼쪽과 오른쪽 자식들의 인덱스는 2i 그리고 2i+1 입니다.
- Q : i 번째 인덱스의 노드의 부모는 어디에 있는가?
- A : i 가 홀수라면 (i-1)/2 이고 i 가 짝수라면 i/2 입니다.
Insert
기존의 힙구조는 문제가 없다고 가정합니다. 새로운 값이 추가됐을 때 최하단 level에 새로운 노드를 추가합니다.
트리 전체를 봤을 때, 문제가 생길 수 있는 곳은 새로 추가된 x 노드입니다. 여기서 부모 노드의 값이 x 왼쪽 자식의 값이 b 라고 가정합니다.
x < c 라면 트리의 문제가 생김 -> 부모 노드와 자식 노드의 값을 exchange (서로 값을 교환해도 x < c < b 는 변하지 않는다.)
위의 방법을 트리의 문제가 생기지 않을 때까지 반복합니다.
시간복잡도 : O(logN)
Delete
Root 에 있는 값을 제거합니다. 제일 밑에 있는 level 의 노드 하나를 Root 로 올립니다. 해당 노드의 값을 x 라고 가정.
크기관계가 문제생긴 곳은 Root 위치가 됩니다.
Root 노드의 왼쪽 오른쪽 자식 노드를 c 그리고 b 라고 가정합니다.
b, c 중 x 보다 작은 값이 있음 -> 부모노드와 자식노드의 값을 exchange
위의 방법을 트리의 문제가 생기지 않을 때까지 반복합니다.
위의 방법을 트리의 문제가 생기지 않을 때까지 반복합니다.
시간복잡도 : O(logN)
Conclusion
힙 구조를 이용하면 우선순위 큐의 삽입과 삭제는 시간복잡도 O(logN) 에 할 수 있다.
사실 코드를 보면 더 명확해짐