우선순위 큐
들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력 되는 방식의 큐
우선 순위 큐 구현 방법 비교
| 구현 방법 | 삽입 | 삭제 |
| 순서 없는 배열 | O(1) | O(n) |
| 순서 없는 연결 리스트 | O(1) | O(n) |
| 정렬된 배열 | O(n) | O(1) |
| 정렬된 연결 리스트 | O(n) | O(1) |
| 힙 | O(logn) | O(logn) |
일반적으로 힙을 이용하여 구현
우선순위가 낮은 데이터가 빠져나오지 못하는 기아현상이 일어날 수 있음
|
[자료구조] 힙 (Heap)
힙 (Heap) 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 힙은 일종의 반정
j3sung.tistory.com
'자료구조' 카테고리의 다른 글
| 그래프 (Graph), 인접 행렬, 인접 리스트 (0) | 2021.05.07 |
|---|---|
| 덱 (Deque) (0) | 2021.05.07 |
| 큐 (Queue), 선형 큐, 원형 큐 (0) | 2021.05.06 |
| 스택 (Stack) (0) | 2021.05.06 |
| 힙 (Heap) (0) | 2021.05.05 |