C++로 쉽게 풀어쓴 자료구조/ 우선순위 큐

우선순위 큐

우선순위 큐란?

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

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

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

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

우선순위 큐 추상 자료형

  • 객체
    • 우선순위를 가진 요소들의 모음
  • 연산
    • insert(item): 우선순위 큐에 항목 item을 추가한다.
    • remove(): 우선순위 큐로부터 가장 우선순위가 높은 요소를 삭제하고 이 요소를 반환한다.
    • find(): 우선순위가 가장 높은 요소를 삭제하지 않고 반환한다.
    • isEmpty(): 우선순위 큐가 공백 상태인지 검사한다.
    • isFull(): 우선순위 큐가 포화 상태인지 검사한다.
    • display(): 우선순위 큐의 모든 요소들을 출력한다.

우선순위 큐의 구현 방법

배열을 사용하는 방법

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

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

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

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

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

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

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

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

연결 리스트를 정렬 시킨 상태로 사용한다면 우선순위가 높은 요소가 앞에 위치하는 것이 유리하다. 삽입 시에는 우선순위 값을 기준으로 삽입 위치를 찾아야 하므로 O(n)이 된다. 삭제 시에는 첫 번째 노드를 삭제하면 되므로 O(1)이다. 결과적으로 배열 사용 방법과 시간 복잡도 차이는 없다.

힙을 사용하는 방법

힙(heap)은 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 힙은 일종의 반 정렬 상태를 유지한다. 즉, 요소들이 완전히 정렬된 것은 아니지만 전혀 정렬되지 않은 것도 아닌 상태를 이용해 우선순위 큐를 구현한다. 힙의 시간 복잡도는 삽입과 삭제 모두 O(log2n)이다.

표현 방법 삽입 삭제
순서 없는 배열 O(1) O(n)
순서 없는 연결 리스트 O(1) O(n)
정렬된 배열 O(n) O(1)
정렬된 연결 리스트 O(n) O(1)
O(log2n)  O(log2n)

힙의 개념

힙은 여러 개의 값들 중에서 가장 큰 값이나 가장 작은 값을 빠르게 찾아내도록 만들어진 자료구조이다. 힙은 간단히 말하면 부모 노드의 키 값이 자식 노드의 키 값보다 항상 큰 이진트리를 말한다.

힙 트리는 이진 탐색 트리와 달리 중복 값을 허용한다.

힙은 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있다는 정도의 느슨한 정렬 상태를 유지한다. 힙의 목적이 삭제 연산에서 가장 큰 값을 효율적으로 찾아내기만 하면 되는 것이므로 전체를 정렬할 이유는 없다.

부모 노드의 키 값이 자식 노드보다 큰 경우를 최대 힙이라 하고, 그 반대의 경우를 최소 힙이라 부른다.

힙의 구현 방법

힙 트리는 완전 이진트리이기 때문에 중간에 비어 있는 요소가 없다. 따라서 힙을 저장하는 효과적인 자료구조는 배열이다.

프로그램 구현을 쉽게 하기 위해 배열의 첫 번째 인덱스는 사용하지 않는다. 트리의 모든 위치의 노드 번호는 새로운 노드가 추가되더라도 변하지 않는다. 예컨대 루트 노드의 왼쪽 노드는 항상 2번이며, 오른쪽 노드는 항상 3번이다.

어떤 노드의 왼쪽이나 오른쪽 자식의 인덱스를 알고 싶으면 다음과 같이 하면 된다.

  • 왼쪽 자식의 인덱스 = 부모의 인덱스 x 2
  • 오른쪽 자식의 인덱스 = 부모의 인덱스 x 2 + 1
  • 부모의 인덱스 = 자식의 인덱스 / 2

삽입 연산

힙에 새로운 요소가 들어오면 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입한다. 하지만 삽입만 하면 힙 트리의 성질이 만족되지 않기 때문에 삽입 후에 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족 시켜주는 과정이 필요하다. 그 과정은 아래와 같다.

1. 번호순으로 가장 마지막 위치에 이어서 새로운 요소 8을 삽입한다.

2. 새로운 요소 8이 부모 노드 4보다 크므로 자리를 교환한다.

3. 새로운 요소 8이 부모 노드 7보다 크므로 자리를 교환한다.

4. 새로운 요소 8이 부모 노드 9 보다 작으므로 자리를 교환하지 않는다.

삭제 연산

힙에서 삭제 연산은 루트 노드를 삭제하는 것이다. 최대 힙에서는 루트가 최댓값을 가지므로 루트 노드를 삭제하고 힙을 재구성 한다.

1. 먼저 루트 노드가 삭제된다. 빈 자리에는 힙의 마지막 노드를 가져온다.

2. 새로운 루트인 3과 자식 노드들을 비교하면 자식 노드가 더 크기 때문에 교환이 일어난다. 이 때 자식들 중에서 더 큰 값과 교환이 일어난다.

3. 아직도 3이 자식 노드들보다 더 작기 때문에 자식과 자리를 교환한다.

4. 3이 자식인 2, 1 보다 크기 때문에 더 이상의 교환은 필요 없다.

힙의 복잡도 분석

힙의 삽입 연산에서 새로운 요소 힙트리를 타고 올라가면서 부모 노드들과 교환을 하게 되는데 최악의 경우, 루트 노드까지 올라가야 하므로 트리 높이에 해당하는 연산이 필요하다. 힙이 완전 이진트리임을 생각해 보면 힙의 높이는 log2n이 되고 따라서 삽입의 시간 복잡도는 O(log2n)이 된다.

삭제도 마찬가지로 마지막 노들르 루트로 가져온 후 자식들과 비교하여 교환하는데, 최악의 경우 가장 아래 레벨까지 내려가야 하므로 트리의 높이만큼 시간이 걸린다. 따라서 삭제의 시간 복잡도도 O(log2n)이 된다.

힙의 응용: 힙 정렬

힙을 사용한 정렬

힙을 이용하면 데이터를 정렬할 수 있는데 방법은 다음과 같다.

  1. n개의 요소를 하나씩 힙에 삽입한다.
  2. 힙에서 n번에 걸쳐 하나씩 요소들을 삭제하고 출력한다.

힙은 삽입과 삭제 모두 log2n이 소요되는데, 1번 과정에서 n번 요소를 삽입하고, 2번 과정에서 n번 요소를 삭제하므로 정렬에 필요한 전체 시간은 nlog2n + nlog2n에 비례하게 된다. 이것은 시간 복잡도 O(nlog2n)으로 삽입 정렬과 같은 간단한 정렬 알고리즘이 O(n2)이 걸리는 것에 비해 매우 좋은 알고리즘 이다.

힙의 응용: 허프만 코드

허프만 코드란?

영어 단어에는 알파벳 ‘e’가 많이 나오는 반면 ‘z’는 많지 않음을 알 수 있다. 각 알파벳의 빈도가 알려져 있다면 이진트리를 이용하여 이 문서를 압축하고 용량을 줄일 수 있다. 이런 종류의 이진트리를 허프만 코딩 트리라고 한다.

어떤 영문 신문에 실린 기사에서 분석한 각 문자의 빈도수가 위 그림과 같다고 하자. 테이블의 각 숫자들은 영문 텍스트에서 해당 글자가 나타나는 빈도수로 e는 z에 비해 123배 더 많이 사용된다는 의미이다.

우리가 흔히 사용하는 아스키(ASCII) 코드는 모든 문자를 동일한 비트수로 표현하는데, 이는 압축의 관점에서 적절하지 않다. 많이 사용하는 문자는 적은 비트 수를 부여하고, 그렇지 않은 문자는 많은 비트수를 부여하면 용량을 줄일 수 있다. 따라서 데이터를 압축할 때는 아스키(ASCII) 코드와 같은 고정 길이 코드를 사용하지 않고 가변 길이 코드를 사용한다.

아래 그림은 구체적으로 FACE 라는 단어를 위 표의 코드를 이용하여 나타낸 것이다. 고정 길이 코드는 순서대로 4비트씩 끊어서 코드를 적거나 읽으면 되는데, 가변 길이 코드로 구성된 코드는 어떻게 해독할까?

이때는 한 비트씩 읽으면서 코드 테이블에 코드가 있으면 한 문자로 처리하면 된다. 예컨대 첫 문자인 0은 테이블에 없으므로 다음 코드까지 읽는다. 01도 테이블에 없으므로 다음 코드를 읽고, 011도 없으므로 다음 코드까지 읽으면 0111은 테이블에서 F에 해당하므로 첫 4비트는 F로 변환한다. 이 방법을 반복하면 FACE라는 원문을 추출할 수 있다.

이런 해독 과정이 가능하려면 모든 가변 길이 코드가 다른 코드의 첫 부분이 되면 안된다. 이러한 특수한 코드를 만들기 위해 이진트리를 사용할 수 있는데, 이런 종류의 코드를 허프만 코드라고 한다.

허프만 코드의 생성 방법

허프만 코드를 만드는 절차는 아래와 같다.

1. 각 문자별로 노드를 생성, 노드의 값은 빈도수가 되고 각 노드는 모두 독립적인 트리의 루트가 된다.

2. 가장 작은 빈도수의 루트를 찾아 묶어 이진트리를 구성한다. 이때 루트의 값은 자식 노드의 값의 합이 된다.

3. 남은 트리에서 가장 작은 빈도수의 루트 2개를 찾아 묶어 이진트리를 구성한다. 10과 8이 선택되고 18, 12, 15를 루트로 하는 3개의 트리가 남는다.

4. 남은 트리에 대해서도 동일한 처리를 한다. 12와 15가 선택되고 이제 18과 27을 루트로 하는 2개의 트리만 남는다.

5. 마지막으로 18과 27을 묶으면 최종 허프만 트리는 1개가 된다.

6. 마지막으로 코드를 할당한다. 트리에서 왼쪽 간선은 비트 1을 나타내고 오른쪽 간선은 비트 0을 나타낸다고 하고, 루트에서부터 그 노드로 이동하면서 코드를 순서대로 적으면 각 문자별로 최종 코드가 된다.

[ssba]

The author

지성을 추구하는 디자이너/ suyeongpark@abyne.com

댓글 남기기

This site uses Akismet to reduce spam. Learn how your comment data is processed.