이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.
https://github.com/AeroCodeX/
우선순위 큐 ADT |
데이터에 우선순위가 존재하여,
저장된 데이터 중, 우선순위가 가장 높은 데이터부터 내보내는 ADT.
우선순위가 있는 메세지 로직에서 주로 사용된다.
분할된 우선순위 큐 ADT (Separated Priority Queue) |
우선순위 큐를 구현할 수 없거나, 우선순위의 범위가 충분히 작은 경우.
각 레벨마다 대응되는 큐를 하나씩 만들어 사용하는 방법도 있다.
우선순위 큐 ADT의 구현과 성능 |
Unsorted List/Array
- 데이터를 삽입할 때 : O(1)
- 가장 큰 값을 탐색할 때 : O(n)
- 가장 큰 값을 제거할 때 : 최댓값 탐색비용 O(n) + 내부 자료구조의 임의의 위치 제거비용.
Sorted List/Array
- 데이터를 삽입할 때 : 들어갈 위치찾기 O(n) + 내부 자료구조의 임의의 위치 삽입비용.
- 가장 큰 값을 탐색할 때 : O(1)
- 가장 큰 값을 제거할 때 : O(1)
Complete Search Binary Tree
- 데이터를 삽입할 때 : O(log n)
- 가장 큰 값을 탐색할 때 : O(log n)
- 가장 큰 값을 제거할 때 : O(log n)
Heap
- 데이터를 삽입할 때 : O(log n)
- 가장 큰 값을 탐색할 때 : O(1)
- 가장 큰 값을 제거할 때 : O(log n)
참고문헌 |
