우선순위 큐(Priority Queue)와 힙(Heap)

우선순위 큐와 힙을 비교해 봄으로써 추상적 데이타 타입과 자료구조의 차이를 명확하게 이해할 수 있다.

우선순위 큐는 추상적 데이타 타입(ADT)의 하나로서, ADT가 정의하는 것은 어떤 블랙 박스 같은 것으로,
그 안에 무엇이 어떻게 들어 있는지에는 관심이 없고, '어떤 일을 할 수 있다'에 초점을 맞춘다.
심지어 그 어떤 일을 할 때 얼마의 시간이 걸리는지에 대해서도 별로 관심이 없다.

우선순위 큐는 다음과 같은 일을 할 수 있다.

1. 큐에 '무엇인가'를 넣을 수 있다. 여기에 숫자로 된 우선순위를 꼬리표로 해서 함께 넣는다.
2. 큐에서 가장 높은 우선순위의 꼬리표가 붙은 '무엇인가'를 꺼낼 수 있다.
3. 2번의 변형으로, 가장 높은 우선순위에 무엇이 있는지 볼 수 있다. (꺼내지 않는다)

add an element to the queue with an associated priority

remove the element from the queue that has the highest priority, and return it

(optionally) peek at the element with highest priority without removing it  

왜 가장 높은 우선순위의 것만 꺼낼 수 있고, 다른 것을 임의로 꺼낼 수도 없는,
그렇게 제약이 많은 것을 생각하느냐고 할 수도 있겠지만,
ADT에서 중요한 개념은 이것이다. 
시간이나 공간 같은 제약을 고려하지 않고, 한정된 수의 요구사항을 명확히 하는 것.
요구사항이 한정되어야 그 다음에, 어떤 방법으로 구현하는 것이 효율적인지 생각할 수 있기 때문이다.

'배열로 구현하지'라고 먼저 생각해 버리면, 배열에서 효율적으로 동작하는 새로운 기능을 추가할 수도 있겠지만,
일의 순서가 그런 것이 아니기 때문이다.

이렇게 우선순위 큐의 기능을 정의하고 나서, 우선순위 큐를 효율적으로 구현하기 위한 자료구조를 생각해 보자.
메모리에 저장된 형태에 대해서 다음과 같은 것을 생각해 볼 수 있다.

1. 배열 - 여기에는 다시 임의 배열과, 정렬된 배열
2. 리스트 - 역시 임의 리스트와, 정렬된 리스트
3. 그리고 다음에 설명할 힙(Heap)

배열과 리스트가 별도의 자료구조인 것은 명확하지만, 임의로 넣은 것과, 정렬된 상태인 것이 다른 것인 이유는,
배열과 리스트에 대한 연산이 다르듯이, 정렬되었는지 여부에 따라 연산의 구현이 확연하게 달라지기 때문이다.

임의 배열을 사용할 경우 우선순위 큐의 구현은 다음과 같이 이루어진다.
1. 넣을 때 - 현재 들어 있는 것들 뒤에 넣는다. O(1)
2. 꺼낼 때 - 우선순위 값을 비교하여 가장 큰 것을 꺼낸다. O(n)

정렬되어 있는 배열을 사용할 경우 우선순위 큐의 구현은 다음과 같이 이루어진다.
1. 넣을 때 - 정렬된 순서에서의 위치를 찾아서 넣는다. O(n)
2. 꺼낼 때 - 맨 앞의 것을 꺼내면 된다. O(1)

n개를 넣고 꺼낼 때 걸리는 시간은, 둘 다 O(n * n)이 된다.

n개를 다 넣고 나서 - 정렬하고 - n개를 순서대로 꺼내는 것은, 우선순위 큐를 쓰고자 하는 목적에도 맞지 않으며,
우선순위 큐의 정의에 정렬 같은 것은 없다. 
다만 이렇게 했을 때 걸리는 시간은 정렬에 걸리는 시간인 O (n log n)으로 낮출 수 있다.

이제 힙에 대해 얘기해 보자.
힙이라는 자료구조를 가지고 얻고자 하는 것은 임의로 넣고 꺼내는 것을 지원하면서, O(n * n)보다 빠른 방법이다.

이를 위해서 힙이라는 자료구조는 개념상으로 바이너리 트리에서, '부모 노드는 자식 노드보다 크다'라는 가정만
유지한다. 당연히 최상위 루트 노드의 값이 가장 크다. 
이를 배열에 저장했을 때 유지되는 내부 형태는, n번째 항목의 자식 노드는 n * 2와, n * 2 + 1 번째에 위치한다. 
그리고 배열에 들어있는 값들은 정렬된 형태도 아니고, 임의 형태도 아니지만, 
맨 앞에는 가장 우선순위가 큰 값을 갖고 있게 된다.

1. 넣을 때 - 맨 뒤에 넣는다. 그리고 형제 노드, 부모 노드와 비교해서 셋 중에 큰 값을 부모 노드로 만든다.
그리고 위로 전파한다. O(log n)에 수행 가능하다.

2. 꺼낼 때 - 맨 앞의 것을 꺼낸다. 그리고 이 자리에는 자식 노드 둘 중에 큰 값을 갖고 올라온다.
그리고 아래로 전파한다. 역시 O(log n)에 수행 가능하다.

따라서 n개를 넣고 꺼낼 때 걸리는 시간은, O(n log n)이 된다.
전체적으로, 정렬에 걸리는 시간과 같은 복잡도를 갖게 되었다. 

여기서 얘기하는 힙은 정확하게는 Binary Heap의 array implementation 이다.

이와 같이 추상적 데이타 타입이 문제에 초점을 둔다면, 자료구조는 해결에 초점을 두고  있다.
인터페이스와 임플리멘테이션도 이와 비슷하게 생각할 수 있을 것이다.

좀 더 자세한 것은 위키피디아에서 Priority Queue와 Heap을 검색해 보기 바란다.

출처 : http://core.egloos.com/