힙 (Heap)

우선 순위 큐

힙

힙의 삽입 연산

힙의 최댓값 삭제 연산

힙 연산의 시간 복잡도

힙 정렬

우선 순위 큐(Priority queues)

우선 순위 큐는 삽입(Insert)과 최댓값 삭제(DeleteMax) 등 두 가지 기본적인 연산을 가지는 자료구조이다. 최댓값 삭제 대신에 최솟값 삭제 연산으로 대체할 수도 있고, 두 삭제 연산을 모두 가지고 있을 수도 있다.

우선 순위 큐를 구현하는 가장 간단한 방법으로 배열과 연결 리스트를 이용하는 방법이 있다.

배열을 이용하여 구현에서 원소를 오름차순으로 정렬하여 두는 경우는 최댓값을 찾거나 삭제하는 것이 O(1) 시간에 가능하지만, 삽입은 원소를 이동해야 하는 경우가 생기므로 O(n) 시간이 필요하다. 원소를 정렬하지 않은 경우는 삽입은 O(1) 시간에 실행할 수 있으나, 최대 원소를 찾아서 삭제하기 위해서는 O(n) 시간을 피할 수 없다.

연결 리스트를 이용하는 경우도 노드를 정렬하여 두는 경우는 DeleteMax를 위해서 O(1) 시간, Insert를 위해서 O(n) 시간을 써야하며, 정렬하지 않은 경우는 DeleteMax를 위하여 O(n), Insert를 위하여 O(1) 시간이 소요된다.

힙(Heap)

힙은 우선 순위 큐(priority queue)를 구현하는 가장 흔한 방법중의 하나이다. 나중에 살펴보겠지만, Insert 연산과 DeleteMax 연산의 시간 복잡도가 모두 [eqn: O(log n)]이다.

힙은 각 노드에 저장되어 있는 값이 자식 노드에 저장되어 있는 값보다 큰 완전 이진 트리이다. 이렇게 정의된 힙은 최대 힙(max heap)이라고 한다. 유사하게 최소 힙(min heap)을 정의할 수 있다. 힙의 왼쪽 부트리와 오른쪽 부트리는 모두 힙이다.

최대 힙의 예

최소 힙의 예

힙의 삽입 연산

힙에서 원소를 삽입하려면 마지막 위치에 노드를 만들어 일단 삽입한다. 그러면 힙이 완전 이진 트리라는 구조 성질(structural property)은 만족하지만 각 노드의 값이 자식 노드보다는 커야한다는 힙 성질(heap property)은 일반적으로 만족하지 않게 된다.

삽입된 노드의 값이 부모 노드의 값보다 작으면 힙 성질을 만족하므로 끝내면 되고, 그렇지 않으면 부모 노드와 서로 바꾼다. 이 과정을 힙의 루트까지 반복하여 삽입 연산을 완성한다.

힙의 최댓값 삭제 연산

힙에서 최댓값은 항상 루트에 있으므로 루트 노드를 제거한 후 나머지 노드들이 힙 성질을 만족하도록 한다. 마지막 노드를 제거하여 루트로 가져와서 힙의 구조 성질을 만족하게 한 다음, 루트에서부터 두 자식 노드와 비교하여 큰 값을 가진 노드와 서로 교환하는 방식을 반복함으로써 힙 성질을 만족하도록 한다.

힙 연산의 시간 복잡도

힙에서 Insert 연산의 시간 복잡도는 얼마나 될까? 새로 삽입된 노드는 최악의 경우 교환을 반복하여 루트 노드가 될 수도 있다. 새로 삽입된 위치에서 루트까지는 이동하기 위하여 몇 번의 교환 연산을 수행하야 하는가? 그리고 각 교환 연산을 위하여 얼마나 시간을 소요하게 되는가?

힙에서 최댓값 삭제 연산을 위해서는 마지막 위치에 있는 노드를 루트로 이동한 다음, 교환을 통하여 적절한 위치까지 이동하게 되는데 최악의 경우는 리프 노드가 될 수 있다. 몇 번의 교환 연산을 통하여 리프 노드까지 이동하게 되는가?

위에서 교환 연산의 횟수는 모두 힙의 루트 노드에서 리프 노드까지의 최대 거리, 즉 힙의 높이(height)가 된다. 힙은 완전 이진 트리이므로 노드의 수가 n이면 높이는 [eqn: log_2 n]을 넘지 않는다.

따라서 위의 두 연산의 시간 복잡도는 모두 [eqn: O(log n)]이다.

힙 정렬(heap sort)

힙에서 Insert와 DeleteMax이 모두 [eqn: O(log n)] 시간에 수행 가능하므로 이 연산을 이용하여 정렬할 수 있다. 정렬할 데이터 n개를 모두 Insert하고 난 후 최댓값을 차례로 삭제하여 보관하면 정렬이 가능하다. 이때는 Insert와 DeleteMax가 모두 n회 실시되므로 힙 정렬의 시간 복잡도는 [eqn: O(n log n)]이 된다.

n개의 데이터를 보관하고 있는 배열을 잘 이용하면 추가적으로 다른 배열을 사용하지 않고도 정렬을 마칠 수 있다. 이런 유형의 알고리즘을 in-place 알고리즘이라고 한다. 힙에서 최댓값을 삭제하면 힙은 배열에서 인덱스가 1부터 n-1까지 사용하게 되므로, 인덱스가 n인 위치에 삭제한 최댓값을 저장한다. 이러한 방식을 반복함으로써 추가적인 메모리를 사용하지 않고 정렬을 완성할 수 있다.

n개의 데이터가 한번에 주어져 있을 때, n개의 데이터로 구성된 힙은 Insert 연산을 n회 실행하는 방식으로 얻은  [eqn: O(n log n)] 시간보다 빠른 [eqn: O(n)] 시간에 만들 수 있다. 그렇다고 힙 정렬의 시간이 빨라지는 것은 아님에 유의한다. 왜냐하면 힙 정렬에서 DeleteMax 연산을 n회 실시하는 것은 피할 수 없기 때문이다.

힙 정렬 (계속)

n개의 데이터로 힙을 만드는 알고리즘을 생각하여 보자. 루트를 제외한 왼쪽 부트리와 오른쪽 부트리가 힙일 때 루트를 포함하여 힙 성질을 만족하도록 만드는 것은 DeleteMax 연산에서 보았듯이 [eqn: O(h)] 시간에 완성할 수 있다. 여기서 h는 트리의 높이이다. 이 과정을 주어진 완전 이진 트리의 레벨이 큰 노드부터 루트까지 순차적으로 실행함으로써 힙을 완성할 수 있다.

이 알고리즘의 시간 복잡도를 [eqn: O(n)]이라고 말할 수 있을까? 주어진 이진 트리의 높이를 k라고 하자. 그러면 노드의 수 n은 [eqn: 2^k <= n < 2^{k+1}]을 만족한다. 레벨 i인 노드에 대해서는 교환 연산이 k-i회 발생하므로 다음과 같이 구할 수 있다.

[eqn: SUM from { 0 <= i <= k-1 } (k-i) 2^i] [eqn: = SUM from { 0 <= i <= k-1 } (i+1) 2^k-i-1]

[eqn: = 2^k SUM from { 1 <= i <= k } i over 2^i] [eqn: = O(n)]