6. Heapsort

힙 정렬의 수행 시간은 O(n \lg n)이다. 병합 정렬과는 다르게, 힙 정렬은 제자리 알고리즘이다: 입력 배열 밖에서 차지하는 메모리는 최대 상수 개이다. 따라서 병합 정렬과 삽입 정렬의 좋은 점만 취했다고 할 수 있다. 또한 힙이라는 유용한 자료 구조를 사용하기도 한다.

6.1. Heaps

이진 힙은 준-완전 이진 트리로 보일 수 있는 배열이다. 트리의 각 노드는 배열의 원소에 대응한다. 이 트리는 맨 아래 층을 제외한 모든 층이 완전히 차 있으며 맨 아래 층은 왼쪽에서부터 차게 된다. 힙을 나타내는 배열은 길이와 힙 크기라는 2개의 특성을 가진다. 트리의 루트는 첫 번째 원소이며, A[i]의 왼쪽 자식 노드는 A[2 \cdot i], 오른쪽 자식 노드는 A[2 \cdot i+1], 부모 노드는 A[\lfloor i/2 \rfloor]가 된다.

이진 힙은 힙 특성을 만족해야 하는데, 최대 힙에서는 최대 힙 특성을 만족하며 이는 루트를 제외한 모든 노드에 대해 부모 노드의 값이 노드의 값 이상인 특성을 말한다. 그러므로 노드의 최대값은 루트가 된다. 이와 반대로 최소 힙에서는 최소 힙 특성을 만족하며 이는 루트를 제외한 모든 노드에 대해 부모 노드의 값이 노드의 값 이하인 특성을 말한다. 그러므로 노드의 최소값은 루트가 된다. 힙 정렬에서는 최대 힙을 쓴다. 힙을 트리로 볼 때 노드의 높이는 리프 노드까지의 최대 거리로, 트리의 높이는 루트의 높이로 정의한다. n개 원소의 힙의 높이는 \Theta(\lg n)이다.

  • MAX-HEAPIFY는 O(\lg n)으로, 최대 힙 특성을 유지한다.
  • BUILD-MAX-HEAP은 선형 시간으로, 정렬되지 않은 입력 배열로부터 최대 힙을 만든다.
  • HEAPSORT은 O(n \lg n)으로, 배열을 제자리에서 정렬한다.
  • MAX-HEAP-INSERT, HEAP-EXTRACT-MAX, HEAP-INCREASE-KEY, HEAP-MAXIMUM은 O(\lg n)으로, 힙 자료 구조로 우선순위 큐를 만든다.

6.2. Maintaining the heap property

MAX-HEAPIFY는 입력 배열 A와 원소 i를 받아서 최대 힙 특성을 유지한다. 이 때 LEFT(i)와 RIGHT(i)를 루트로 하는 이진 트리가 힙임을 가정하며, A[i]가 자식 노드보다 작다면 힙 특성이 깨지므로 A[i]를 내려보내서 (아래의 어떤 노드와 치환해서) 최대 힙 특성을 유지시킨다.

MAX-HEAPIFY(A, i)
l = LEFT(i)
r = RIGHT(i)
if l ≤ A.heap-size and A[l] > A[i]
    largest = l
else
    largest = i
if r ≤ A.heap-size and A[r] > A[largest]
    largest = r
if largest ≠ i
    exchange A[i] with A[largest]
    MAX-HEAPIFY(A, largest)

A[i]가 최대 원소라면 A[i]를 루트로 하는 이진 트리는 힙이 되어 알고리즘이 종료된다. 그렇지 않다면 A[i]는 A[l] 또는 A[r] 중 하나와 치환되어 재귀적으로 해당 부분 트리에서 MAX-HEAPIFY를 호출한다. MAX-HEAPIFY는 \Theta(1)의 시간 복잡도를 노드의 높이 h만큼 수행하므로 O(\lg h)이 된다.

6.3. Building a heap

MAX-HEAPIFY를 아래에서부터 위로 적용해 배열을 최대 힙으로 바꿀 수 있다.

BUILD-MAX-HEAP(A)
A.heap-size = A.length
for i = floor(A.length / 2) downto 1
    MAX-HEAPIFY(A, i)

이 때 루프 내 불변 조건은 다음과 같다:

루프 시마다, i + 1부터 n까지의 노드는 최대 힙의 루트이다.

이 불변 조건은 끝까지 유지되며, 알고리즘의 정당성을 보장한다.

초기화 : floor(n / 2) + 1, …, n은 리프 노드이므로 루트이다.

유지 : 노드 i의 자식 노드는 i보다 번호가 크므로 최대 힙의 루트이다. 따라서 MAX-HEAPIFY(A, i)의 사전조건을 만족하며, 수행 후에는 i가 최대 힙의 루트가 되어 i가 1 감소한 시점에서도 해당 루프 불변 조건을 유지하게 된다.

종료 : i = 0에서, 노드 1, …, n은 최대 힙의 루트가 된다.

MAX-HEAPIFY는 O(\lg n) 수행 시간이고, BUILD-MAX-HEAP은 O(n) 번만큼 MAX-HEAPIFY를 부르므로, 수행 시간의 상한은 O(n \lg n)이 되지만, 실제 수행시간은 \sum_{h=0}^{\lfloor \lg n \rfloor} \lceil \frac{n}{2^{h+1}} \rceil O(h) = O(n  \sum_{h=0}^{\lfloor \lg n \rfloor}  \frac{h}{2^h})  = O(n) 이 된다. 따라서 이는 선형 시간이다.

똑같은 방식으로 최소 힙도 만들 수 있다.

6.4. The heapsort algorithm

힙 정렬은 우선 BUILD-MAX-HEAP을 통해 최대 힙을 만든다. 최대 원소는 루트인 맨 앞 원소에 저장되므로 이를 맨 뒤 원소와 교환한다. 이후 힙에서 맨 뒤 원소 (현 최대 원소)를 배제하면 힙 특성을 깨는 건 루트 원소 (이전 맨 뒤 원소) 뿐이다. 이에 대해 MAX-HEAPIFY(A, 1)을 수행하면 된다. 힙 정렬은 이를 반복한다.

HEAPSORT(A)
BUILD-MAX-HEAP(A)
for i = A.length downto 2
    swap A[1] with A[i]
    A.heap_size -= 1
    MAX-HEAPIFY(A, 1)

BUILD-MAX-HEAP이 O(n \lg n), MAX-HEAPIFY가 O(\lg n)에 n – 1번 불리므로 전체 시간복잡도는 O(n \lg n)이다.

6.5. Priority queues

힙 정렬의 가장 유명한 응용 예는 우선순위 큐로, 힙과 같이 최대 우선순위 큐와 최소 우선순위 큐의 2가지 형태로 나뉜다.

우선순위 큐를 가진 자료 구조인데, 최대 우선순위 큐는 다음의 연산을 지원한다:

  • INSERT(S, x) : x를 S에 삽입
  • MAXIMUM(S) : 최대 키를 가진 값을 반환
  • EXTRACT-MAX(S) : 최대 키를 가진 값을 제거한 뒤 반환
  • INCREASE-KEY(S, x, k) : x의 키를 새 값 k로 증가시킴

최소 우선순위 큐는 이 반대이다. 우선순위 큐는 힙으로 구현해서 힙에 대응하는 우선순위 큐의 원소를 제어할 수 있다.

HEAP-MAXIMUM은 MAXIMUM 연산을 \Theta(1)에 수행한다.

HEAP-MAXIMUM(A)
return A[1]

HEAP-EXTRACT-MAX는 EXTRACT-MAX 연산을 구현하며, 수행 시간은 $O(\lg n)$이다.

HEAP-EXTRACT-MAX(A)
if A.heap-size < 1
    error "heap underflow"
max = A[1]
A[1] = A[A.heap-size]
A.heap-size -= 1
MAX-HEAPIFY(A, 1)
return max

HEAP-INCREASE-KEY는 INCREASE-KEY 연산을 구현하며, 힙 특성을 유지하기 위해 키를 증가시킨 뒤 부모 노드를 계속해서 탐색하면서 부모의 키가 증가된 키보다 작지 않을 때까지 부모와 키값을 교환한다. 수행 시간은 $O(\lg n)$이다.

HEAP-INCREASE-KEY(A, i, key)
if key < A[i]
    error "new key is smaller than current key"
A[i] = key
while i > 1 and A[PARENT(i)] < A[i]
    exchange A[i] with A[PARENT(i)]
    i = PARENT(i)

MAX-HEAP-INSERT는 INSERT 연산을 구현하며, HEAP-INCREASE-KEY를 1회 수행하므로 시간은 $O(\lg n)$이다.

MAX-HEAP-INSERRT(A, key)
A.heap-size += 1
A[A.heap-size] = -INF
HEAP-INCREASE-KEY(A, A.heap-size, key)

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Google photo

Google의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 /  변경 )

%s에 연결하는 중