9. Priority Queue

1. Prioity Queue

 

Priority Queue란 여러 요소를 집어넣고 나올 때는 우선순위에 따라 나오도록하는 자료구조이다.

즉, item을 빼낼 때마다 가장 크나 작은 아이템이 Queue에서 remove된다.

 

API는 다음과 같다.

void insert(Key v)

Key delMax()

boolean isEmpty()

 

만약,. N개의 item중에서 가장 큰 M개의 item을 찾고 싶다고 하자.

가장 쉬운 방법은 sorting이다. 하지만, 만약 N개의 item을 저장할 충분한 공간이 없다면 어떻게 할까?

mininum prioity queue에 key값을 집어넣고 queue의 size가 M보다 커질 때 제거한다면 가장 작은 item이 제거된다.

item을 넣음을 반복하고 M보다 커질 때마다 item을 제거한다. 이렇게하면, size를 N만큼 확보하지 않고도 가장 크거나/작은 M개의 item을 찾는 문제를 해결할 수 있다. 성능은 NlogM이 되어 M이 상수이므로 ~N의 성능이다.

 

2. Binary heap

출처 : wikimdeia

 

binary heap이란 완전이진트리(complete binary balanced tree)이면서 parent가 children보다 더 큰 tree이다.

tree의 index는 위와 같이 증가하며, 배열로 구현할 경우 배열의 index이다

Index가 k인 노드에 대해, 부모노드는 [k/2]이고, 자식노드는 2k와 2k+1이다.

 

만약 특정 node가 규칙을 깰 경우 부모/자식 노드와 서로 비교하고 교환함으로서 다시 규칙성을 회복할 수 있다.

Insert의 경우 가장 큰 index+1에 추가하고, 규칙을 깰 경우, 부모노드와 교환하고 그래도 깰 경우 그 상위의 부모노드와 다시 교환하는 것을 반복함으로서 규칙성을 회복한다.

Remove의 경우, root node와 가장 큰 index와 위치를 교환한 후, root node는 제거하거고 root node자리로 간 node는 교환을 통해 규칙성을 회복시킨다. 

binary heap은 완전이진트리이므로 삽입과 제거는 tree의 높이인 logN의 성능이 보장되고, 최대/최소값 검색은 contant time에 이루어진다.

 

※Immutability of keys※

Priority Queue는 일반적인 Queue, Stack과는 다르게 Key의 값이 변경될 경우 Prioity 규칙성이 깨질 수 있다.

따라서 구현시에 초기 내부 요소를 정하고, private final 와 같은 키워드를 이용하여 내부의 요소를 변경불가능하게 하거나 외부에서 직접 접근하여 priority queue가 변경되지 않도록 해야한다. Priority Queue의 Key로 변경불가능한 읽기전용인Wapper type의 객체를 사용할 수도 있다. 이러한 immutable한 data type을 사용하는 이점 중 하나는 디버깅을 쉽게 해주며, prioity queue 나 symbol table의 안전한 사용을 보장한다는 것이다.

 

3. Heap sort

 

Heap sort의 방식은 다음과 같다.

1) min/max heap을 생성한다(bottom-up 방향 교환으로 규칙성 회복)

2) min/max key를 반복적으로 제거한다.

 

1번과정의 실행시간은 수학적으로 C(N) <= 2N이고, 2번과정은 C(N) <= 2NlogN이다.

Heap sort는 stability는 보장하지 않지만, 추가공간 사용이 없어 merge sort의 단점을 보완하고, NlogN의 성능을 보장하여 quick sort의 단점을 보완한다. 하지만 내부루프가 quick sort에 비해 길고, quick sort와는 다르게 인접한 배열의 인덱스를 참조하는 공간지역성을 충분히 활용하지 못하여, 캐시메모리가 거의 모든 곳에 존재하는 현대 컴퓨팅에서는 성능이 잘 나오지 않는다고 한다.

 

응용예시

※ Molecular dynamic simulation ※

이것은 2차원 격자안에서 여러개의 운동하는 입자들이 비탄성 충돌을 할 때, 시간이 지나면서 어떻게 격자 내의 입자들이 운동할 것인지를 보여주는 시뮬레이션이다. 가장 쉽게 생각할 수 있는 해결방법은 각각의 입자를 객체로 구현하고, 매 시간 텀(dt)마다 모든 입자를 추적하고, 가능한 모든 입자쌍에 대해 충돌여부를 조사하는 것이다. 그리고 두 입자에 대해 충돌이 일어난 경우 물리법칙에 의해 두 입자의 속도값을 바꾼다. 이런 경우, 실행시간은 입자쌍 수를 모두 조사해야 하므로 N개 중에서 2개를 선택하는 조합이므로 N(N-1) 개의 조합이 존재하고, 이것은 qudratic한 time이 된다. 따라서 입자의 개수가 매우 많은 경우 사실상 시뮬레이션은 불가능하다. 

또 한가지의 해결책은 먼저 초기상태이후 입자쌍에 대해 충돌이 발생할 때의 시간정보를 가진 Event객체를 만들어 priority queue에 넣는다. 처음에는 qudratic time이 걸리게 된다. 그리고 delMin으로 최솟값을 제거한다. 그것이 가장 첫번째 충돌 Event가 된다. 그리고 그 충돌한 두개의 입자의 속력을 충돌결과에 의해 값을 변경하고, 다시 두개의 입자에 대해서만 충돌시간을 계산한다. 이것은 ~NlogN의 시간이 걸린다. 그리고 그 이후에 prioity queue에서 값을 꺼냈을 때 그것이 이전에 충돌했던 입자와의 충돌을 계산한 것이였다면, 해당 충돌은 무효가 된다. 왜냐하면 이전에 충돌한적있는 입자는 이미 해당 Event발생시점에는 경로가 변경되었기 때문이다. 이런 방식으로 prioity queue를 이용하여 최소시간 Event를 꺼내는 방식을 사용하면 특별히 어떤 dt를 이용할 것인지를 결정할 필요없이 시뮬레이션을 ~NlogN으로 구현할 수 있다.