우선순위 큐

우선순위 큐란?

도로에서 먼저 진입하는 차가 먼저 가게 되지만, 만일 구급차나 소방차가 나타나면 모든 자동차들은 이러한 긴급 차량을 위하여 도로를 양보해야 한다. 이러한 긴급 차량들은 도로 교통법에 의하여 높은 우선순위(priority)를 갖고 있기 때문이다. 컴퓨터에서도 우선순위 개념이 필요할 때가 있는데, 네트워크 패킷 중에서 네트워크 관리와 관련된 것들은 다른 일반 패킷보다 우선순위를 가진다.

우선순위 큐는 바로 이러한 우선순위의 개념을 큐에 도입한 자료구조이다.보통의 큐는 선입선출(FIFO)의 원칙에 의하여 먼저 들어온 데이터가 먼저 나가게 되는데 우선순위 큐(priority queue)는 데이터들이 우선순위를 가지고 있어 우선순위가 높은 데이터가 먼저 출력된다.

우선순위 큐는 사실 가장 일반적인 큐로 볼 수 있는데, 우선순위 큐를 이용하여 스택이나 큐도 얼마든지 구현할 수 있기 때문이다. 예컨대 데이터가 들어온 시각이 빠른 것을 높은 우선순위로 처리하면 큐처럼 동작하고, 늦게 들어온 것을 높은 우선순위로 처리하면 스택으로 사용할 수 있다.

우선순위 큐는 배열, 연결 리스트 등 여러 방법으로 구현이 가능하지만 가장 효율적인 구조는 힙(heap)이다.

우선순위 큐 추상 자료형

우선순위 큐의 구현 방법

배열을 사용하는 방법

정렬되지 않은 배열을 이용하는 방법

정렬되지 않은 배열을 사용하게 되면 삽입은 가장 간단하다. 기존 요소의 맨 끝에 붙이면 된다. 따라서 삽입의 시간 복잡도는 O(1)이다. 그러나 삭제를 할 경우 처음부터 끝까지 모든 요소를 찾아야 하기 때문에 복잡도는 O(n)이 된다. 물론 요소가 삭제된 다음, 뒤에 있는 요소들을 앞으로 이동시켜야 하는 부담도 있다.

정렬된 배열을 이용하는 방법

정렬된 배열은 정렬되지 않은 배열과 반대이다. 삽입시에 모든 요소를 찾고 삽입시 다른 요소들을 움직여야 하기 때문에 시간 복잡도는 O(n)이 되고, 삭제시에는 가장 뒤에 있는 것을 삭제하면 되기 때문에 O(1)이 된다.

Untitled

연결 리스트를 사용하는 방법

정렬되지 않은 연결 리스트를 이용하는 방법

연결 리스트의 경우 배열과 달리 삽입과 삭제 시 노드들의 이동은 필요 없다. 정렬이 안 된 리스트라면 삽입 시에 첫 번째 노드로 삽입하는 것이 유리하다. 이때의 시간 복잡도는 O(1)이다. 삭제 시에는 포인터를 따라서 모든 노드를 방문하고 가장 우선순위가 높은(혹은 낮은) 노드를 찾아야 한다. 이 경우 시간 복잡도는 O(n)이다.

정렬되지 않은 연결 리스트를 이용하는 방법