본문 바로가기

# Foundation/자료구조

우선순위 큐 ADT

이 블로그의 모든 예제코드는 깃허브에서도 볼 수 있습니다.
아래의 포스트는 개인적인 용도로 내용을 요약한 것 입니다.

    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)



참고문헌

마이크로 소프트 ㅡ 우선순위 큐 패턴






'# Foundation > 자료구조' 카테고리의 다른 글

힙 ADT  (0) 2019.02.08
이진트리 ADT  (0) 2019.02.06
트리 ADT  (0) 2019.02.06
그래프 ADT  (0) 2019.02.06
덱 (데크)  (0) 2019.02.04