[Algorithm Part 1] 4. PriorityQueue

이전에 배운 collection의 ADT(e.g., stack, queue)는 삽입 순서에 기반해 객체를 삭제했다.

이번 글에서는, 객체 값에 기반해 객체를 삭제하는 collection의 ADT(=PQ)를 살펴볼 것이다.

PQ에는 2가지 방식이 존재한다.

1). 가장 높은 값을 가진 객체를 삭제하는 방식과 2). 가장 낮은 값을 가진 객체를 삭제하는 방식이 존재한다.

 

PQ를 통해 다음과 같은 과정을 쉽고 빠르게 수행할 수 있다.

1. 수집한 객체들 중 가장 큰 객체 5개를 찾는다.
2. 기존 객체들에 10개의 새로운 객체를 추가한 후, 가장 큰 객체 3개를 찾는다.

---

Priority Queue

Priority Queue는 객체의 집합을 가지고 있는 동시에, 추가/제거 연산을 지원하는 ADT다.

이때, 제거 연산은 가장 높은 값 혹은 낮은 값을 가진 객체를 집합에서 제거함과 동시에 반환(return)한다.

---

1. Implementation 1: unordered array

data structure: 정수 배열(id[])을 사용한다. 정렬 상태를 유지하지 않는다.

 

1. insert: 마지막 인덱스에 객체를 삽입한다.

2. delete: $N$번의 비교 연산을 통해 최대/최소 객체를 찾아 반환 및 삭제한다.

2. Implementation 2: ordered array

data structure: 정수 배열(id[])을 사용한다. 정렬 상태를 유지한다.

 

1. insert: 평균 $\frac{N}{2}$번의 비교 연산을 통해 올바른 위치에 객체를 삽입해 정렬 상태를 유지한다.

2. delete: 마지막 인덱스 객체를 반환 및 삭제한다.

---

3. Binary heap

Data Structure

다음 속성을 만족하는, 배열 기반의 완전 이진 트리(pq[])을 사용한다.

• 인덱스 1부터 사용한다. 즉, 0은 비운다. (부모 노드와 자식 노드의 이동을 편하게 하기 위해)
• 부모 노드는 자식 노드보다 커야 한다.
• 1번으로 인해, 인덱스 k노드의 부모 노드는 k/2이고, 자식 노드는 2k, 2k+1이다.

 Operations

1. swim: 자식 노드가 부모 노드보다 작을 때까지 부모 노드와 자식 노드의 위치를 바꾼다.

2. sink: 부모 노드가 자식 노드보다 클 때까지, 부모 노드와 자식 노드의 위치를 바꾼다.

3. insert: 마지막 인덱스에 노드를 삽입한 후, swim 연산을 한다.

4. delete: root 노드와 마지막 노드의 위치를 바꾼 후, sink 연산을 한다.

---

Performance

implementation	insert	delmax	max
unordered array	1	N	N
ordered array	N	1	1
binary heap	$\log N$	$\log N$	1

immutability

PQ에 삽입된 객체는 수정이 안된다고 가정한다. 즉, immutable data type이라고 가정한다.

참고로, immutable data type으로 SW를 구현하는 것이 안전하고 좋다.

classes should be immutable unless there's a very good reason to make them mutable... If a class cannot be made immutable you should still limit its immutability as much as possible. (by Joshus Bloch (Java architect))

---

Heap sort

binary heap을 이용한 heap sort에 대해 살펴보겠다.

Algorithm

• 정렬할 모든 객체를 binary heap에 넣어 max heap으로 초기화시킨다.
• 반복적으로, binary heap에서 최대 값을 가진 객체를 가져온다.

heap sort

Performance

	initalize	delete max value
heap sort	$\le$ 2N	$\le 2N \log N$

heap sort는 유일하게 in-place이며, $N \log N$ 시간 복잡도를 가진다.

하지만, 실무에서는, quick sort를 더 자주 사용한다. 이유는 다음과 같다.

1. 긴 반복문: 반복문 내부가 quick 정렬보다 길다. (e.g., 각 자식 노드 비교 연산)
2. 캐시 성능 저하: heap 정렬은 먼 배열 항목과 비교하므로, 캐시 미스가 날 확률이 높다. 반면에, 다른 정렬 알고리즘은 근처 배열 항목과 비교하므로 캐스 미스가 날 확률이 낮다.
3. stable 정렬이 아니다.