Week2_우선순위 큐_개념

1. 우선순위 큐란?

*자료구조까지 학습한 분이라면 '큐(Queue)'의 개념은 아실 거예요.

큐는 '선입선출', 즉 먼저 들어간 데이터가 먼저 나가는 자료구조를 말하죠.

 

그런데 왜 '우선순위'라는 말이 붙는건지?? 

'우선순위 큐'는 우선순위가 높은 데이터부터 나가는 구조입니다! 그러니까 들어온 순서랑은 무관하다는 이야기죠.

 

 

*우선순위 큐 ADT

-우선순위 큐 ADT는 각 데이터를 (키, 원소)로 저장한답니다.

 

이 ADT 메소드에는 무엇이 있는지 한번 살펴볼까요?

 

• 주요 메소드

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

• 일반 메소드

• integer size(): 큐의 데이터 수 반환
• boolean isEmpty(): 큐가 비어 있는지 여부 반환

• 접근 메소드

• element minElement():
• element minKey():

• 예외

• emptyQException():
• fullQException():

 

 

 

---

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

<의사코드 정리>

입력: 리스트 -> 출력: 정렬된 리스트

 

1. P <= 빈 우선순위 큐

2. L 비어있지 않으면, 리스트에서 앞에서부터 원소 삭제하고 e에 저장한 다음 -> 그 e를 P에 삽입

3. P 비어있지 않으면, P(큐)에서 최솟값 삭제하고 e에 저장한 다음 -> 그 e를 L의 뒤부터 삽입

4. return

 

	무순리스트	순서리스트
	우선순위 큐 데이터들 리스트에 임의 순서로 저장	우선순위 큐 데이터들 리스트에 키 정렬 순서로 저장
insertItem  (1회 기준)	O(1)	O(n)
removeMin minKey minElement (1회 기준)	O(n)	O(1)

 

이렇게 리스트의 종류는 순서를 기준으로 2가지가 있는데요, 그럼 우선순위 큐를 각각 무순리스트, 순서리스트로 만드는 알고리즘은 무엇일까요?

 

1) 선택 정렬

5

4

3

2

1

위 표처럼 리스트 하나(L)가 있어요. 이 리스트를 이제 우선순위 큐에 담을 건데... 일단은 그냥 넣어보기로 해요~

5

4

3

2

1

-> 우선순위 큐에 다 담았고, 원래 리스트 L은 비어 있는 상태랍니다. 

이제 우리는 이 큐에 담긴 원소들을 L로 다시 넣어서 정렬된 리스트 L'을 만들건데, 최솟값부터 차례대로 L에 넣을거예요!

가장 작은 원소를 찾으려면 n번 탐색해야 해요. 

그리고 그 다음으로 작은 원소는 n-1 번 탐색해야 하죠. (앞에서 가장 원소는 이미 나갔으니까)

...이런 식으로 빈 큐가 될 때까지 이 큐에서 데이터를 삭제시켜요! (-> removeMin)

 

 

2) 삽입 정렬

선택 정렬

삽입 정렬

(작성 중)