Priority Queue(우선순위 큐)와 리스트기반 구현

 

Priority Queue

 

큐는 먼저 삽입되는 데이터가 먼저 나가는 FIFO(First In First Out) 형식의 자료구조이다. 

: 우선순위 큐는, 삽입 순서가 아닌, 우선순위가 높은 데이터가 먼저 나가는 형태의 자료구조로 

구현 방식에 따라 running-time이 달라질 수 있다. 

 

 

 

 

Sequeunce-based priority queue(시퀀스 기반 우선순위 큐)

1. Selected List(선택정렬) O(n^2)

: 1.unsorted list와 함께 구현되는 우선순위 큐 방식

→ 무순리스트S → 우선순위 큐 P

- 우선순위 큐에서 삭제할 때 모든 원소를 비교

- 우선순위 큐에 삽입 하는 데 n개의 원소 삽입하므로 O(n)-time

- 정렬순서로 삭제하는 데 n + (n-1) + ```  + 1 sum : 최소값찾기 O(n^2) time 수행

insert	O(n)
removeMin	O(n^2)

 

Unsorted list (무순리스트)

insert	O(1)
removeMin	O(n)

 

 

 

 

 

2. Insertion Sort(삽입정렬) O(n^2)

: 2. sorted list 와 함께 구현되는 우선순위 큐 방식

→ 순서리스트S → 우선순위 큐 P

- 제자리정렬 알고리즘 중 하나 

- 우선순위 큐에 삽입 하는 데 삽입과 동시에 정렬하며 모든 원소 비교

- 우선순위 큐에 삽입 하는데 n개의 원소 기존에 있던 원소와 비교하며 삽입 1 + ```+ n sum : O(n^2)-time

- 우선순위 큐에서 삭제하는데 정렬 그대로 유지한 채 최소값 하나씩 삭제 O(n)-time

 

insert	O(n^2)
removeMin	O(n)

 

Sorted List

insert	O(n)
removeMin	O(1)

 

 

- In-place Insertion/selection Sort(제자리 삽입,선택정렬) O(n^2)

O(1)-space or,, O(log n) -space(재귀)암묵적 허용

: 외부적인 자료구조를 사용하지 않고, 제자리에서 선택정렬과 삽입정렬을 구현한다. 

→ 정렬된 배열 앞에서부터 비교하여, 자신의 위치를 찾아 제자리에 삽입한다. 

- 무시할 만큼의 메모리 공간. 현 배열 안에서 정렬이 다 이뤄짐 

→ 추가적인 공간이 필요한 경우 공간복잡도가 높음

- 입력된 리스트의 이부가 그것 자체로 우선순위 역할을 한다. 

 

 

시퀀스 기반의 우선순위 큐 구현은, 최악의 경우 O(n^2)-time 의 시간복잡도가 된다. 
따라서, 속도면에서 이를 보안하기 위한 개념이 Heap(힙) 자료구조이다.