1. 우선순위큐

🔍우선순위 큐(Priority Queue)

접근메소드

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

일반메소드

• integer size(): 큐의 사이즈를 반환
• boolean isEmpty(): 큐가 비었는지 반환.

원소 접근 메소드

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

예외

• emptyQueueException(): 비어있는 큐에 대해 삭제나 원소접근을 시도할 경우 발생
• fullQueueException(): 큐가 가득 차있을때 삽입을 시도할 경우 발생

 

🔍우선순위 큐를 이용한 정렬

비교 가능한 원소 집합을 정렬하는데 우선순위 큐 이용가능

• 연속적인 insertItem(e,e)작업으로 원소들을 하나씩 삽입.
• 연속적인 removeMin()작업으로 원소들을 정렬순서로 삭제

우선순위 큐의 슈도코드

Alg PQ-Sort(L)
input list L
output sorted list L

1. P ← empty priority queue
2. while(!L is Empty()):
	e←L.removeFirst()
	P.insertItem(e)
3. while(!P.isEmpty())
	e←P.removeMin()
	L.addLast(e)
4. return

위는 일반 리스트에서 우선순위큐로 넣어주고,

우선순위 큐에서 정렬된 값을 다시 리스트에 넣어주는 식의 정렬을 사용한 알고리즘이다.

만약 삽입과 삭제시간이 상수시간일 경우 O(n)의 시간이 난다.

그러나 현실적으로는 그렇지 않다.

※L,P: 일반(generic): 어떤 곳에든 써먹을 수 있는 알고리즘이다.

🔍리스트에 기초한 우선순위 큐

무순리스트로 구현(선택정렬)

• 우선순위 큐의 항목들을 리스트에 임의 순서로 저장한다.
• insertItem(): O(1)의 시간 소요, 항목을 리스트 맨앞 또는 맨뒤에 막 삽입해도 되므로
• removeMin, minkey, minElement: O(n)의 시간소요: 최소키를 찾기위해 전체 리스트를 순회한다.

순서리스트로 구현(삽입정렬)

• 우선순위 큐의 항목들을 리스트에 키 정렬 순서로 저장한다.
• insertItem(): O(n)의 시간소요, 최소키를 삽입하기 위해 전체 리스트를 순회한다.
• removeMin, minkey, minElement: O(1) 의 시간소요, 맨앞 또는 맨뒤를 뽑으면 되기 때문.

🔍우선순위큐는 공간이 2개가 반드시 필요한가?

공간을 2개나 사용한다면 공간적으로 비효율적이기 때문에 1공간 안에서 수행할 수 있으면 좋을 것이다.

O(n)공간을 차지하는 외부의 우선순위 큐로 리스트를 정렬해왔음.

오직 상수 메모리만 사용하면 알고리즘이 제자리에서 수행한다함.(일부 상수로 추가되는 공간은 괜찮음)

제자리 선택정렬: 리스트를 변경하는 대신 swapElements를 사용함.

• 선택정렬 알고리즘으로 앞에서부터 정렬순서의 1순위부터 채워나감

제자리 삽입정렬: 리스트를 변경하는 대신 swapElememts를 사용함.

• 삽압정렬 알고리즘으로 뒤의 것을 맞는 순서에 삽입해감.

// 선택정렬 알고리즘
Alg inPlaceSelectionSort(A)
	input array A of n keys
	output sorted array A
	
1. for pass <- 0 to n-2
		minLoc <- pass
		for j <- (pass + 1) to n - 1
			if(A[j] < A[minLoc])
				minLoc <- j
		A[pass] <-> A[minLoc]
2. return

// 삽입정렬 알고리즘
Alg inPlaceInsertionSort(A)
	input array A of n keys
	output sorted array A
	
1. for pass <- 1 to n-1
		save <- A[pass]
		j <- pass-1
		while((j>=0)&(A[j]>save))
			A[j+1]<-A[j]
			j<-j-1
		A[j+1]<-save
2. return

둘다 O(n^2)의 시간복잡도

초기 리스트가 완전히 정렬된 경우 삽입정렬이 더 빠르다.