PS/Algorithm

[ Algorithm ] 우선순위 큐

HUIcode 2023. 6. 30. 19:46

우선순위 큐 ADT : 임의의 데이터 항목이 삽입되며, 일정한 순서(우선순위가 높은 원소부터 삭제)에 의해 삭제되는 데이터 구조. '큐'와 데이터 항목을 저장하고 삽입과 삭제가 가능하다는 점은 동일.

- 우선순위 큐에 저장되는 각 데이터 항목은 (키, 원소)쌍으로 정의됨 ex. 우편물의 경우 (주소, 우편물) / 답안지의 경우(학번, 점수)

 

우선순위 큐 구현방식

1) 단순 리스트 사용

2) 힙(heap) 사용

구현 방식 삽입 시간복잡도 삭제 시간복잡도
리스트 O(1) O(n)
힙(heap) O(log n) O(log n)

우선순위 큐 ADT 메쏘드 

1) 주요 메쏘드 

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

 

2) 일반 메쏘드

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

 

3) 접근 메쏘드 

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

 

4) 예외

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

우선순위 큐를 이용한 정렬 : 데이터 원소들을 일정한 순서에 의해 재배치 하는 것 / 정렬 과정에서 원소들을 임시 보관하는 저장소를 이용할때 우선 순위 큐를 저장소로 이용하여 정렬할 수 있음

 

1) 일반적 정렬 PQ-Sort

Alg PQ-Sort(L)
	input list L
	output sorted list L
    
1. P ← empty priority queue //큐 초기화
2. while(!L.isEmpty())
	e ← L.removeFirst() //리스트의 첫번째 원소를 pop
    P.insertItem(e) //큐에 pop한 원소를 push
3. while(!P.isEmpty())
	e ← P.removeMin()
    L.addLast(e) //큐의 제일 작은 원소부터 리스트에 삽입
4. return

 

→ 리스트L과 우선순위 큐P가 배열 or 연결리스트 중 어느것으로 구현되었는지와 무관(일반 데이터구조)하게 작동함

→ PQ-Sort 알고리즘은 우선순위 큐의 상세구현에 따라 달라짐

 

  • 무순리스트(unordered list)로 구현하는 경우
    • 우선순위 큐의 항목들을 리스트에 임의순서로 저장
    • 성능  ㅣ insertItem - O(1) : 리스트의 맨 앞 혹은 맨 뒤에 삽입 , removeMin & minKey & minElement - O(n) : 최소 키를 찾기 위해 전체 리스트를 순회

 

  • 순서리스트(ordered list)로 구현하는 경우
    • 우선순위 큐의 항목들을 리스트에 키 순서로 저장
    • 성능 ㅣ insertItem - O(n) : 항목을 삽입할 곳을 찾아야 함, removeMin & minKey & minElement - O(1) : 최소 키를 가진 항목이 리스트의 맨 앞에 존재

 

  • 힙(Heap)으로 구현하는 경우

 

2) 선택 정렬(selection-sort)

: 우선순위 큐가 무순리스트로 구현됨 

: 시간 복잡도 - O(n^2)

 

3) 삽입 정렬(insertion-sort)

: 우선순위 큐가 순서리스트로 구현됨

: 시간 복잡도 - O(n^2)

 

4) 제자리 정렬

  • 제자리 선택 정렬
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

 

선택정렬과 삽입정렬 비교

1) 공통점

  • 수행 시간 : O(n^2) 
  • 기억공간 사용량 : 제자리 정렬의 경우 모두 O(1) 공간 사용

 

2) 차이점

  • 초기 입력 리스트가 완전히/거의 정렬된 경우 : 제자리 삽입 정렬 >>> 제자리 선택 정렬
  • 데이터 원소의 교환 작업에 시간이 많이 소요되는 경우 : 제자리 삽입 정렬 <<< 제자리 선택 정렬