[알고리즘] 우선순위 큐(1) - 설명

우선순위큐ADT는 임의의 데이터 항목이 삽입되며, 일정한 순서에 의해 삭제되는 데이터구조이다

우선순위 큐에 저장되는 데이터 항목은 (키, 원소)쌍으로 정의된다

Ex) 우편배달부가A는 우편물을 가방에 아무렇게나 담아서 각각의 주소에 도착했을 때, 우편물을 가방에서 찾아서 배달한다.

반면, 우편배달부B는 우편물을 가방에 순서대로 담아서 각각의 주소에 도착했을 때, 우편물을 꺼내서 바로 배달한다.

이 경우 주소는 키가되고, 원소는 우편물이 된다

A의 경우, 삽입은 빠르지만, 삭제가 느리다

B의 경우, 삽입은 느리지만, 삭제가 느리다

우선순위 큐ADT메소드

1) 주요메소드

insertItem(k, e) - 키k인 원소e를 큐에 삽입

element removeMin() - 큐로부터 최소 키를 가진 원소를 삭제하여 반환

2) 일반메소드

integer size() - 큐의 항목 수를 반환

boolean isEmpty() - 큐가 비어 있는지 여부를 반환

3) 접근메소드

element minElement() - 큐에서 최소 키를 가진 원소를 반환

element minKey() - 큐에서 최소 키를 반환

4) 예외메소드

emptyQueueException() - 비어 있는 큐에 대해 삭제나 원소 접근을 시도할 경우 발령

fullQueueException() - 만원 큐에 대해 삽입을 시도할 경우 발령

-----------------------------------------------------------------------------------------------------------------------------------------------------------------

정렬이란 데이터 원소들의 키순서에 의해 재배치하는 것이다

앞으로 선택정렬, 삽입정렬, 힙정렬등 여러가지 정렬을 배울 것이다

선택정렬은 A의 경우처럼 무순리스트처럼 구현되고, 삽입정렬은 B의 경우처럼 순서리스트로 구현된다

두개의 정렬 모두 O(n^2)시간에 실행되고, insertItem과 removeMin모두 O(n)시간을 소요한다

그리고, 두개의 정렬모두 추가공간이O(n)만큼 필요하지만, 제자리 정렬을 사용하여 공간사용량을 줄일 수 있다

Ex              선택정렬        삽입정렬

5 4 2 3 1        5 4 2 3 1

1 4 2 3 5        4 5 2 3 1

1 2 4 3 5        2 4 5 3 1

1 2 3 4 5        2 3 4 5 1

1 2 3 4 5        1 2 3 4 5

1 2 3 4 5        1 2 3 4 5

출처

제목: 알고리즘 원리와 응용

저자: 국형준

출판사: 21세기사