우선순위 큐

1. 우선순위 큐 ADT

ADT란?
순수하게 기능이 무엇인지를 나열한 것을 가리켜 '추상 자료형' 혹은 ADT라고 한다.

임의의 데이터 항목이 삽입되며, 일정한 순서에 의해 삭제되는 데이터구조.

데이터 항목 --> (키, 원소) 쌍

 

큐와 우선순위 큐의 비교

큐: 삽입된 순서 그대로 삭제.

우선순위 큐: 키 순서에 따라 삭제.

 

2. 우선순위 큐 응용

경매, 주식 등의 응용 방법 => 정렬

 

3. 우선순위 큐 ADT 메쏘드

주요 메쏘드

• insertItem(k, e): 키 k인 원소 e를 큐에 삽입
• element removeMin(): 큐로부터 최소 키를 가진 원소를 삭제하여 반환

일반 메쏘드: 큐 size 반환, 큐 empty 여부 봔환

접근 메쏘드: 최소키 원소, 최소키 반환

 

4. 우선순위 큐를 이용한 정렬

1. 무순리스트 구현: 우선순위 큐의 항목들을 리스트에 임의 순서로 저장한다. O(1) -> O(n) => 선택 정렬
2. 순서리스트 구현: 우선순위 큐의 항목들을 리스트에 키 순서로 저장한다. O(n) -> O(1) => 삽입 정렬

 

5. 제자리 정렬

원래 리스트 자체를 위한 내부 공간 이외에 추가로 O(1) 크기의 외부 공간만 사용 => 제자리 수행

• 리스트의 앞 부분을 정렬 상태로 유지
• 리스트에서 원소를 삭제하는 대신 원소들의 자리를 맞바꾼다

5.1 제자리 선택 정렬

초기: 입력 리스트 전체 -> 우선순위 큐

우선순위 큐의 크기 -> 한 칸씩 좁아짐.

5.2 제자리 삽입 정렬

초기: 우선순위 큐 비어있음.

우선순위 큐의 크기 -> 한 칸씩 넓어짐.

 

6. 선택 정렬과 삽입 정렬 비교

공통점

1. O(n^2) 시간
2. 중첩 반복문 (내부 반복문: 선형 탐색, 외부 반복문: 정렬 단계)
3. 기억공간 소요량: 제자리 버전 : O(1)
4. 구현이 단순함 -> 입력 크기 n이 작은 경유 유용함

차이점

if) 초기 입력 리스트 -> 완전히 or 거의 정렬

    제자리 삽입 정렬 > 제자리 선택 정렬

이유: 거의 정렬이 됐다면, 제자리 삽입 정렬 알고리즘의 내부 반복문이 매번 O(1) 시간만 소요 => 전체 O(n) 시간

else if) 데이터원소끼리의 교환 작업에 많이 시간이 걸리는 경우

    제자리 삽입 정렬 < 제자리 선택 정렬

이유: 패스마다 O(1)회 수행 but 제자리 삽입 정렬 -> 최악일 경우에는 O(n) 회 교환 작업 수행

점근적 수행 기간은 O(n^2)으로 동일하더라도 실제 수행 시간은 제자리 삽입 정렬이 느림.