Priority Queue(우선순위 큐)
우선 순위를 가진 항목들을 저장하는 큐
우선 순위가 높은 데이터가 먼저 나가게 됨.
응용 분야 : 시뮬레이션, 네트워크 트래픽 제어, OS의 작업 스케줄링
우선순위 큐 ADT
데이터 : 우선순위를 가진 요소들의 모음
연산 :
insert(item) : 우선순위 큐에 항목 item을 추가
remove( ) : 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이를 반환함.
find( ) : 우선순위가 가장 높은 요소를 삭제하지 않고 반환함.
isEmpty( ) : 우선순위 큐가 공백 상태인지 검사
isFull( ) : 우선순위 큐가 포화 상태인지 검사
display( ) : 우선순위 큐의 모든 요소들을 출력
우선순위 큐의 가장 중요한 연산 : insert 연산(요소 삽입), remove 연산(요소 삭제)
우선순위 큐 구현 방법
배열을 이용한 구현
연결리스트를 이용한 구현
힙(heap)을 이용한 구현
완전 이진 트리
우선순위 큐를 위해 만들어진 자료구조
일종의
반 정렬 상태
(정렬되지 않은 상태)를 유지함.
우선순위 큐 구현 방법 비교
표현 방법
삽입
삭제
순서 없는 배열
O(1)
O(n)
순서 없는 연결리스트
O(1)
O(n)
정렬된 배열
O(n)
O(1)
정렬된 연결리스트
O(n)
O(1)
힙
O(log n)
O(log n)
O(1) < O(log n) < n
$O(log n)= O(log_2n)$