우선순위 큐

우선순위 큐 ADT

(키, 원소) 쌍의 형태로 저장

예시 : 탑승 대기자(ex. 키: 예약 시간, 원소: 승객), 경매(ex. 키: 가격, 원소: 가격을 제시한 사람), 주식 시장 등

 

주요 메쏘드

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

일반 메쏘드

• integer size() : 큐의 항목 수를 반환
• boolean isEmpty() : 큐가 비어있는지 여부를 반환

접근 메쏘드

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

예외

• emptyQueuException() : 비어있는 큐에 삭제/접근 시도할 경우
• fullQueueException() : 만원 큐에 삽입 시도할 경우

 

우선순위 큐를 이용한 정렬

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

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

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

• 연속적인 insertItem 작업으로 원소들을 하나씩 삽입
• 연속적 removeMin 작업으로 원소들을 정렬 순서로 삭제
• 실행시간 : 우선순위 큐의 구현에 따라 다름

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

1. 무순리스트로 구현 ▶ 선택정렬
   • 우선순위 큐의 항목들을 리스트에 임의 순서로 저장
   • 성능
     • insertItem : O(1) 
       맨앞/맨뒤에 삽입할 수 있음
     • removeMin, minKey, minElement : O(n)
       최소 키를 찾기 위해 전체 리스트를 순회해야함
2. 순서리스트로 구현 ▶ 삽입정렬
   • 우선순위 큐의 항목들을 키 정렬 순서로 저장
   • 성능
     • insertItem : O(n) 
       항목을 삽입할 곳을 찾아야함
     • removeMin, minKey, minElement : O(1)
       최소 키가 리스트의 맨 앞에 있음

선택 정렬

• 우선순위 큐의 일종
• 우선순위 큐를 무순 리스트로 구현
• 실행시간
  • n회의 insertItem 작업을 통해 원소들을 우선순위 큐에 삽입하는데 O(n) 소요
  • n회의 removeMin 작업을 통해 원소들을 우선순위 큐로부터 정렬 순서로 삭제하는데 n + (n-1) + ... + 1 소요
  • Total : O(n^2) 시간 소요

삽입 정렬

• 우선순위 큐의 일종
• 우선순위 큐를 순서 리스트로 구현
• 실행시간
  • n회의 insertItem 작업을 통해 원소들을 우선순위 큐에 삽입하는데 0 + 1 + 2 + ... + (n-1) + n 소요
  • n회의 removeMin 작업을 통해 원소들을 우선순위 큐로부터 정렬 순서로 삭제하는데 O(n) 소요
  • Total : O(n^2) 시간 소요

제자리 정렬

• 위의 선택/삽입 정렬 모두 θ(n)공간을 차지하는 외부의 우선선위 큐를 사용해 리스트를 정렬함
• 원래 리스트 자체를 위한 공간 이외에 O(1) 공간만을 사용할 때, 제자리에서 수행한다고 말한다. 이때 메모리를 줄일 수 있다.
• 제자리 선택 정렬
  • 우선순위 큐를 입력 리스트의 일부라고 생각
  • 원래 있던 리스트에서 가장 작은 원소를 찾아 리스트의 맨 앞에 위치시킴
  • 리스트의 두번째 위치부터 가장 작은 원소를 찾아 두번째 위치에 위치시킴
  • 위와 과정 계속 반복
  • 즉, 리스트의 앞부분을 정렬 상태로 유지 & 리스트를 변경하는 대신 swapElements 이용
• 제자리 삽입 정렬
  • 우선순위 큐를 입력 리스트의 일부라고 생각
  • 처음에는 첫번째와 두번째 인덱스를 비교해 첫번째 인덱스가 더 클 경우 두 원소 교환
  • 두번째 인덱스와 세번째 인덱스 비교, 다시 두번째 인덱스와 첫번째 인덱스 비교해 더 작은 원소가 앞으로 가게 함
  • 위의 과정 계속 반복
  • 리스트의 앞부분을 정렬 상태로 유지 & 리스트를 변경하는 대신 A[j + 1] ← A[j] 사용