자료구조
우선순위 큐 (Prioity Queue)
J3SUNG
2021. 5. 6. 21:00
728x90
우선순위 큐
들어온 순서와 상관없이 우선순위가 높은 데이터가 먼저 출력 되는 방식의 큐
우선 순위 큐 구현 방법 비교
| 구현 방법 | 삽입 | 삭제 |
| 순서 없는 배열 | 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