우선순위 큐와 힙(heap) (1) 힙이 필요한 이유

보통의 큐(queue)는 먼저 들어온 데이터가 먼저 나가는 자료구조입니다. 그런데 들어온 순서가 아닌 중요도에 따라서 일을 처리해야 하는 경우 큐는 사용할 수 없습니다. 이 때 우선순위 큐를 사용할 수 있습니다.

우선순위 큐는 모든 데이터가 우선순위를 가지고 있고 들어온 순서와 관계 없이 우선순위가 높은 데이터가 먼저 출력되는 자료구조입니다.

 

우선순위 큐는 배열, 연결리스트로도 구현이 가능하지만 보통 힙으로 구현하는데,

힙으로 구현하기 전에 배열을과 연결리스트를 이용해 구현해보고, 힙으로 구현한 것을 보면서 왜 힙을 쓰는지 알아봅시다.

 

1. 정렬되지 않은 배열을 이용하여 우선순위 큐를 구현한 경우

정렬이 되지 않았다는 말은 우선순위가 뒤죽박죽 섞였다는 말입니다. 그 과정을 그림으로 나타내면 다음과 같습니다.

정렬되지 않은 배열을 사용하여 구현한 경우

(참고로 첫 번째 원은 배열의 1번째 인덱스 즉 array[0]에 해당하고 두 번째 원은 배열의 2번째 인덱스 array[1]에 해당합니다. 원 안에 들어 있는 숫자는 우선순위를 뜻합니다. 즉 그림에서는 배열의 네 번째 인덱스가이 가장 높은 우선순위를 가지고 있다고 할 수 있겠죠?)

 

삽입이 굉장히 간단합니다. 위 그림으로 설명하면 기존의 배열에 새롭게 들어온 4를 그냥 맨 뒤에 붙여주면 되거든요.

하지만 삭제는 복잡해집니다. 아까 우선순위 큐에서는 우선순위가 높은 요소를 먼저 처리한다고 했었죠? 삭제 시 우선순위가 가장 높은 12를 처리해야 하기 때문에 스캔 과정을 통해 12의 배열 인덱스를 찾아내고 삭제한 후 빈자리를 없애기 위해 한칸씩 이동시켜야 합니다. 꽤나 복잡한 작업이 필요하게 되죠. 그림과 같습니다.

 

스캔 과정을 통해 가장 우선순위 높은 인덱스를 찾아내고

값을 처리하고 그 빈자를 한칸씩 이동하여 채우게 됩니다.

따라서 복잡도가 삽입시에는 O(1), 삭제 시에는 O(n)이 됩니다.

 

2. 정렬된 배열을 이용하여 우선순위 큐를 구현한 경우

정렬되지 않은 배열을 이용하는 경우와 반대입니다. 삽입이 복잡해지고 삭제가 간단해집니다.

삽입 과정에서 우선순위에 따라 배열의 순서가 이루어지며 삭제 시에는 맨 뒤에 있는 요소를 삭제하면 됩니다.

 

삽입과정부터 그림으로 살펴 보겠습니다.

먼저 스캔 과정을 통해 '4'가 들어갈 위치를 탐색합니다. 2와 5 사이에 들어가야 하겠죠?

위치를 찾아냈다면 5~12까지의 요소를 한 칸씩 뒤로 밀고 그 자리에 4를 집어 넣습니다.

정렬되지 않은 배열과는 반대로 삽입이 복잡해졌네요.

 

하지만 삭제는 간단해졌습니다. 가장 뒤에 있는 요소인 12를 지우기만 하면 되거든요.

 

삭제

연결리스트를 사용해서 우선순위 큐를 구현하는 경우는 어떻게 될까요?

---

 

---

먼저 정렬이 되지 않은 연결리스트를 사용하는 경우입니다.

삭제 시 가장 우선순위가 높은 노드를 찾아야하므로 스캔 과정이 필요합니다. 12를 찾기 위해서는 모든 노드를 방문하면서 찾아야 합니다.

 

삽입 시는 첫 번째 노드에 삽입하는 것이 유리하므로 첫 번째 노드에 바로 삽입하게 됩니다.

 

4를 삽입하는 경우

연결리스트에서 삽입을 하는 것은 간단합니다. 기존 head가 가지고 있던 주소를 새로운 노드의 링크필드에 넣어주고 새로운 노드의 주소를 기존 head에 넣어주면 됩니다.

 

마지막으로 정렬이 된 연결리스트는 어떻게 될까요?

정렬된 연결리스트는 위 그림과 같습니다. 우선순위가 가장 높은 노드를 첫 번째 노드로 하는 것이 계산에 유리하므로 다음과 같은 구조를 가지게 됩니다. 삭제 시에는 첫 번째 노드를 삭제하면 되므로 복잡도는 O(1)이 됩니다.

 

삽입 시에는 탐색을 통해 들어갈 노드의 위치를 확인해야 하기 때문에 복잡도가 O(n)이 됩니다.

결과적으로 연결리스트를 사용하더라도 배열을 사용한 방법과 시간 복잡도 차이가 별로 없습니다. 그래서 우선순위 큐에서는 힙(heap)이라는 형태로 구현하게 됩니다. 힙에 대해서는 다음 글에서 알려드리도록 하겠습니다.