힙

이 주제에 대한 튜토리얼은 여기에서 확인할 수 있다.

힙은 배열 안에 있는 이진 트리로, 부모/자식 포인터를 사용하지 않는다. 힙은 트리 내 노드의 순서를 결정하는 "힙 속성"에 따라 정렬된다.

힙의 일반적인 사용 사례:

우선순위 큐를 구축한다.
힙 정렬을 지원한다.
컬렉션의 최소(또는 최대) 요소를 빠르게 계산한다.
프로그래밍을 모르는 친구들에게 깊은 인상을 준다.

힙의 속성

힙에는 *최대 힙(max-heap)*과 최소 힙(min-heap) 두 종류가 있다. 이 두 힙은 트리 노드를 저장하는 순서에 따라 구분된다.

최대 힙에서는 부모 노드가 자식 노드보다 더 큰 값을 가진다. 최소 힙에서는 모든 부모 노드가 자식 노드보다 더 작은 값을 가진다. 이를 "힙 속성(heap property)"이라 부르며, 이 속성은 트리의 모든 노드에 적용된다.

예시:

이 예시는 최대 힙이다. 모든 부모 노드가 자식 노드보다 크기 때문이다. (10)은 (7)과 (2)보다 크다. (7)은 (5)와 (1)보다 크다.

이 힙 속성으로 인해 최대 힙은 항상 가장 큰 값을 트리의 루트에 저장한다. 최소 힙은 루트에 항상 가장 작은 값을 저장한다. 힙 속성은 힙이 우선순위 큐로 사용될 때 "가장 중요한" 요소에 빠르게 접근할 수 있게 해주기 때문에 유용하다.

참고: 힙의 루트에는 최대 또는 최소 요소가 위치하지만, 다른 요소들의 정렬 순서는 예측할 수 없다. 예를 들어, 최대 힙에서 최대 요소는 항상 인덱스 0에 위치하지만, 최소 요소가 반드시 마지막에 위치하는 것은 아니다. 최소 요소는 리프 노드 중 하나라는 것만 보장되며, 어느 리프 노드인지는 알 수 없다.

힙과 일반 트리의 비교

힙은 이진 탐색 트리를 대체하는 개념이 아니다. 두 구조는 유사점과 차이점을 모두 가지고 있다. 주요 차이점은 다음과 같다.

노드 순서. 이진 탐색 트리(BST)에서는 왼쪽 자식 노드가 부모 노드보다 작아야 하고, 오른쪽 자식 노드가 부모 노드보다 커야 한다. 힙은 이런 규칙을 따르지 않는다. 최대 힙(max-heap)에서는 두 자식 노드가 부모 노드보다 작아야 하고, 최소 힙(min-heap)에서는 두 자식 노드가 부모 노드보다 커야 한다.

메모리 사용. 전통적인 트리는 저장하는 데이터 외에 추가 메모리가 필요하다. 노드 객체와 왼쪽/오른쪽 자식 노드를 가리키는 포인터를 위한 공간을 할당해야 한다. 힙은 단순한 배열만 사용하며 포인터가 필요 없다.

균형 유지. 이진 탐색 트리는 대부분의 연산이 O(log n) 성능을 보장하려면 "균형"을 유지해야 한다. 데이터를 무작위 순서로 삽입하고 삭제하거나, AVL 트리나 레드-블랙 트리 같은 구조를 사용해 균형을 맞출 수 있다. 하지만 힙은 전체 트리를 정렬할 필요가 없다. 힙 속성만 만족하면 되므로 균형 문제가 발생하지 않는다. 힙의 구조적 특성 덕분에 O(log n) 성능을 보장한다.

탐색 속도. 이진 트리에서 탐색은 빠르지만, 힙에서는 느리다. 힙은 최대(또는 최소) 노드를 맨 앞에 배치하고 상대적으로 빠른 삽입과 삭제를 지원하는 데 초점을 맞추므로 탐색이 주된 목적이 아니다.

배열 안에 담긴 트리

트리 구조를 배열로 구현하는 것이 이상하게 보일 수 있지만, 시간과 공간 측면에서 모두 효율적이다.

앞서 예제에서 사용한 트리를 다음과 같이 배열에 저장한다:

[ 10, 7, 2, 5, 1 ]

이것이 전부다. 이 간단한 배열 외에 추가 저장 공간이 필요하지 않다.

그렇다면 포인터를 사용하지 않고 어떻게 부모 노드와 자식 노드를 구분할 수 있을까? 좋은 질문이다! 트리 노드의 배열 인덱스와 그 부모 및 자식 노드의 배열 인덱스 사이에는 명확한 관계가 존재한다.

i가 노드의 인덱스라면, 다음 공식으로 부모와 자식 노드의 배열 인덱스를 구할 수 있다:

parent(i) = floor((i - 1)/2)
left(i)   = 2i + 1
right(i)  = 2i + 2

right(i)는 단순히 left(i) + 1이다. 왼쪽과 오른쪽 노드는 항상 서로 인접해 있다.

이 공식을 예제에 적용해 보자. 배열 인덱스를 채워 넣으면 배열에서 부모와 자식 노드의 위치를 알 수 있다:

Node	Array index (`i`)	Parent index	Left child	Right child
10	0	-1	1	2
7	1	0	3	4
2	2	0	5	6
5	3	1	7	8
1	4	1	9	10

이 배열 인덱스가 실제로 트리 그림과 일치하는지 직접 확인해 보자.

참고: 루트 노드 (10)는 부모가 없다. -1은 유효한 배열 인덱스가 아니기 때문이다. 마찬가지로 노드 (2), (5), (1)은 자식이 없다. 해당 인덱스가 배열 크기를 초과하기 때문이다. 따라서 계산한 인덱스가 실제로 유효한지 항상 확인해야 한다.

최대 힙(max-heap)에서 부모의 값은 항상 자식의 값보다 크거나 같다. 이는 모든 배열 인덱스 i에 대해 다음이 성립해야 함을 의미한다:

array[parent(i)] >= array[i]

예제 힙의 배열이 이 힙 속성을 만족하는지 확인해 보자.

보듯이, 이 공식은 포인터 없이도 어떤 노드의 부모나 자식 인덱스를 찾을 수 있게 해준다. 포인터를 역참조하는 것보다 복잡하지만, 이것이 트레이드오프다. 메모리 공간을 절약하는 대신 추가 계산이 필요하다. 다행히 이 계산은 빠르고 O(1) 시간만 걸린다.

배열 인덱스와 트리 내 위치 사이의 관계를 이해하는 것이 중요하다. 다음은 15개의 노드를 4개의 레벨로 나눈 더 큰 힙이다:

이 그림의 숫자는 노드의 값이 아니라 노드를 저장하는 배열 인덱스다! 다음은 트리의 각 레벨에 해당하는 배열 인덱스다:

공식이 작동하려면 부모 노드가 배열에서 자식 노드보다 먼저 나타나야 한다. 위 그림에서 이를 확인할 수 있다.

이 방식에는 한계가 있다. 일반 이진 트리에서는 가능하지만 힙에서는 불가능한 작업이 있다:

현재 가장 낮은 레벨이 완전히 채워지지 않으면 새로운 레벨을 시작할 수 없다. 따라서 힙은 항상 다음과 같은 형태를 가진다:

참고: 힙으로 일반 이진 트리를 흉내낼 수는 있지만, 공간이 낭비되고 배열 인덱스를 비어 있음으로 표시해야 한다.

간단한 퀴즈! 다음과 같은 배열이 있다고 하자:

[ 10, 14, 25, 33, 81, 82, 99 ]

이 배열은 유효한 힙일까? 정답은 '그렇다'이다. 낮은 값에서 높은 값으로 정렬된 배열은 유효한 최소 힙(min-heap)이다. 이 힙을 다음과 같이 그릴 수 있다:

각 노드에 대해 힙 속성이 성립한다. 부모는 항상 자식보다 작기 때문이다. (높은 값에서 낮은 값으로 정렬된 배열이 항상 유효한 최대 힙(max-heap)인지 직접 확인해 보자.)

참고: 하지만 모든 최소 힙이 반드시 정렬된 배열인 것은 아니다! 한 방향으로만 작동한다. 힙을 다시 정렬된 배열로 바꾸려면 힙 정렬을 사용해야 한다.

더 많은 수학!

궁금한 독자를 위해 힙의 특정 속성을 설명하는 몇 가지 공식을 소개한다. 이 공식을 외울 필요는 없지만, 가끔 유용하게 쓰일 수 있다. 이 섹션은 건너뛰어도 무방하다!

트리의 높이는 루트 노드에서 가장 아래 리프 노드까지 가는 단계의 수로 정의한다. 좀 더 정확히 말하면, 높이는 노드 간 가장 긴 경로의 엣지 수를 의미한다. 높이가 h인 힙은 h + 1개의 레벨을 가진다.

다음 힙은 높이가 3이므로 4개의 레벨로 구성된다:

노드 수가 n인 힙의 높이는 *h = floor(log2(n))*이다. 이는 새로운 레벨을 추가하기 전에 항상 가장 아래 레벨을 완전히 채우기 때문이다. 예제 힙은 15개의 노드를 가지므로 높이는 floor(log2(15)) = floor(3.91) = 3이다.

가장 아래 레벨이 완전히 채워진 경우, 해당 레벨은 2^h개의 노드를 포함한다. 그 위의 나머지 트리는 2^h - 1개의 노드를 가진다. 예제의 숫자를 대입해 보면, 가장 아래 레벨은 8개의 노드를 가지며, 이는 2^3 = 8과 일치한다. 위쪽 세 레벨은 총 7개의 노드를 포함하며, 2^3 - 1 = 8 - 1 = 7과 같다.

따라서 전체 힙의 총 노드 수 n은 2^(h+1) - 1이다. 예제에서 2^4 - 1 = 16 - 1 = 15이다.

n개의 노드를 가진 힙에서 높이가 h인 노드는 최대 *ceil(n/2^(h+1))*개 존재한다.

리프 노드는 항상 배열 인덱스 *floor(n/2)*부터 n-1까지 위치한다. 이 사실을 활용해 배열로부터 힙을 빠르게 구성할 수 있다. 믿기지 않는다면 예제를 통해 직접 확인해 보라. ;-)

이것으로 여러분의 하루를 밝힐 수학적 사실 몇 가지를 마친다.

힙으로 무엇을 할 수 있는가?

힙에 요소를 추가하거나 제거한 후에도 최대 힙(max-heap)이나 최소 힙(min-heap)이 유효한 상태를 유지하려면 두 가지 기본 연산이 필요하다:

shiftUp(): 요소가 부모보다 크다면(최대 힙) 또는 작다면(최소 힙) 부모와 교환한다. 이렇게 하면 트리 위로 이동한다.
shiftDown(): 요소가 자식보다 작다면(최대 힙) 또는 크다면(최소 힙) 트리 아래로 이동한다. 이 연산은 "heapify"라고도 한다.

위로 또는 아래로 이동하는 작업은 O(log n) 시간이 소요되는 재귀적 절차다.

기본 연산을 기반으로 하는 다른 연산들은 다음과 같다:

insert(value): 새로운 요소를 힙의 끝에 추가한 후 shiftUp()을 사용해 힙을 수정한다.
remove(): 최대값(최대 힙) 또는 최소값(최소 힙)을 제거하고 반환한다. 요소를 제거한 후 빈 자리를 채우기 위해 마지막 요소를 루트 위치로 이동시킨 다음 shiftDown()을 사용해 힙을 수정한다. (이를 "extract min" 또는 "extract max"라고도 한다.)
removeAtIndex(index): remove()와 유사하지만, 루트뿐만 아니라 힙의 어떤 요소든 제거할 수 있다. 새로운 요소가 자식과 순서가 맞지 않을 경우 shiftDown()을, 부모와 순서가 맞지 않을 경우 shiftUp()을 호출한다.
replace(index, value): 노드에 더 작은(최소 힙) 또는 더 큰(최대 힙) 값을 할당한다. 이로 인해 힙 속성이 무효화되므로 shiftUp()을 사용해 수정한다. (이를 "decrease key" 또는 "increase key"라고도 한다.)

위의 모든 연산은 위로 또는 아래로 이동하는 작업이 비용이 많이 들기 때문에 O(log n) 시간이 소요된다. 더 많은 시간이 필요한 연산도 있다:

search(value): 힙은 효율적인 검색을 위해 설계되지 않았지만, replace()와 removeAtIndex() 연산은 노드의 배열 인덱스가 필요하므로 해당 인덱스를 찾아야 한다. 시간: O(n).
buildHeap(array): (정렬되지 않은) 배열을 힙으로 변환하기 위해 insert()를 반복적으로 호출한다. 이를 효율적으로 수행하면 O(n) 시간에 완료할 수 있다.
힙 정렬: 힙은 배열이므로 그 고유한 속성을 이용해 배열을 낮은 순서에서 높은 순서로 정렬할 수 있다. 시간: O(n log n).

힙에는 peek() 함수도 있다. 이 함수는 힙에서 요소를 제거하지 않고 최대값(최대 힙) 또는 최소값(최소 힙)을 반환한다. 시간: O(1).

참고: 힙을 사용할 때 가장 일반적으로 수행하는 작업은 insert()로 새로운 값을 추가하거나 remove()로 최대값 또는 최소값을 제거하는 것이다. 둘 다 O(log n) 시간이 소요된다. 다른 연산들은 우선순위 큐와 같은 고급 사용 사례를 지원하기 위해 존재한다. 우선순위 큐에서는 항목이 큐에 추가된 후에도 그 "중요도"가 변경될 수 있다.

힙에 삽입하기

구체적인 예제를 통해 삽입 과정을 자세히 살펴보자. 값 16을 다음 힙에 삽입해 보자:

이 힙의 배열은 [ 10, 7, 2, 5, 1 ]이다.

새 항목을 삽입할 때 첫 번째 단계는 배열의 끝에 추가하는 것이다. 배열은 다음과 같이 변한다:

[ 10, 7, 2, 5, 1, 16 ]

이 배열은 다음 트리와 일치한다:

(16)이 마지막 행의 첫 번째 빈 공간에 추가되었다.

불행히도, (2)가 (16) 위에 위치하면서 힙 속성이 더 이상 만족되지 않는다. (이것은 최대 힙이므로 더 큰 숫자가 더 작은 숫자 위에 위치해야 한다.)

힙 속성을 복원하기 위해 (16)과 (2)를 교환한다.

여전히 작업이 끝나지 않았다. (10)도 (16)보다 작기 때문이다. 삽입된 값이 부모보다 작아지거나 트리의 최상단에 도달할 때까지 부모와 계속 교환한다. 이 과정을 shift-up 또는 sifting이라고 하며, 모든 삽입 후에 수행된다. 이 과정은 너무 크거나 작은 숫자가 트리 위로 "떠오르게" 만든다.

최종적으로 다음과 같은 결과를 얻는다:

이제 모든 부모가 자식보다 다시 커졌다.

shift-up에 필요한 시간은 트리의 높이에 비례하므로 O(log n) 시간이 걸린다. (배열 끝에 노드를 추가하는 시간은 **O(1)**이므로 속도를 늦추지 않는다.)

루트 노드 제거

다음 트리에서 (10)을 제거해 보자:

맨 위에 생긴 빈 자리는 어떻게 처리할까?

삽입할 때는 새로운 값을 배열의 끝에 추가했다. 이번에는 반대로, 배열의 마지막 요소를 가져와 트리의 맨 위에 배치한 후 힙 속성을 복원한다.

이제 (1)을 아래로 이동(shift-down)시키는 방법을 살펴보자. 최대 힙의 속성을 유지하려면 가장 큰 숫자가 맨 위에 있어야 한다. 교환할 후보는 (7)과 (2) 두 가지다. 이 세 노드 중 가장 큰 숫자를 맨 위에 배치해야 하므로, (7)을 선택해 (1)과 교환한다. 그 결과는 다음과 같다.

노드가 자식이 없거나 두 자식보다 클 때까지 계속 아래로 이동시킨다. 이 힙에서는 한 번 더 교환하면 힙 속성이 복원된다.

아래로 이동하는 데 걸리는 시간은 트리의 높이에 비례하며, O(log n) 시간이 소요된다.

참고: shiftUp()과 shiftDown()은 한 번에 하나의 잘못된 요소만 수정할 수 있다. 여러 요소가 잘못된 위치에 있다면, 각 요소에 대해 이 함수를 한 번씩 호출해야 한다.

임의의 노드 제거하기

대부분의 경우 힙의 루트에 있는 객체를 제거한다. 힙이 그렇게 설계되었기 때문이다.

하지만 임의의 요소를 제거해야 할 때도 있다. 이는 remove()의 일반화된 버전이며, shiftDown()이나 shiftUp()을 사용할 수 있다.

다음 예제 트리에서 (7)을 제거해 보자:

배열은 다음과 같다:

[ 10, 7, 2, 5, 1 ]

요소를 제거하면 최대 힙 또는 최소 힙 속성이 깨질 수 있다. 이를 해결하기 위해 제거할 노드와 마지막 요소를 교환한다:

[ 10, 1, 2, 5, 7 ]

마지막 요소는 반환할 요소이다. removeLast()를 호출해 힙에서 제거한다. 이제 (1)은 자식인 (5)보다 작지만 트리에서 더 높은 위치에 있으므로 순서가 맞지 않다. 이를 수정하기 위해 shiftDown()을 호출한다.

하지만 아래로 이동시키는 것만 해결해야 하는 상황은 아니다. 새로운 요소를 위로 이동시켜야 할 때도 있다. 다음 힙에서 (5)를 제거하는 경우를 생각해 보자:

이제 (5)는 (8)과 교환된다. (8)이 부모보다 크므로 shiftUp()을 호출해야 한다.

배열로 힙 생성하기

배열을 힙으로 변환하는 것은 유용하다. 이 과정은 단순히 배열 요소를 재배치하여 힙 속성을 만족시키는 것이다.

코드로 표현하면 다음과 같다:

  private mutating func buildHeap(fromArray array: [T]) {
    for value in array {
      insert(value)
    }
  }

배열의 각 값에 대해 insert()를 호출한다. 간단하지만 효율적이지는 않다. 이 방법은 O(n log n) 시간이 소요된다. n개의 요소가 있고 각 삽입에 log n 시간이 걸리기 때문이다.

수학적 배경을 살펴보면, 모든 힙에서 배열 인덱스 n/2부터 n-1까지의 요소는 트리의 리프 노드다. 이 리프 노드는 건너뛰어도 된다. 나머지 노드만 처리하면 되는데, 이들은 하나 이상의 자식을 가진 부모 노드이므로 순서가 잘못되었을 가능성이 있다.

코드로 표현하면 다음과 같다:

  private mutating func buildHeap(fromArray array: [T]) {
    elements = array
    for i in stride(from: (nodes.count/2-1), through: 0, by: -1) {
      shiftDown(index: i, heapSize: elements.count)
    }
  }

여기서 elements는 힙의 배열이다. 첫 번째 리프가 아닌 노드부터 시작해 배열을 거꾸로 순회하며 shiftDown()을 호출한다. 이 간단한 루프는 건너뛴 리프 노드와 함께 이 노드들을 올바른 순서로 배치한다. 이를 Floyd의 알고리즘이라고 하며, O(n) 시간만 소요된다. 효율적이다!

힙 탐색

힙은 빠른 탐색을 위해 설계된 구조가 아니다. 하지만 removeAtIndex()를 사용해 임의의 엘리먼트를 제거하거나 replace()로 엘리먼트의 값을 변경하려면 해당 엘리먼트의 인덱스를 알아야 한다. 탐색은 이를 수행하는 한 가지 방법이지만, 속도가 느리다는 단점이 있다.

이진 탐색 트리에서는 노드의 순서에 따라 빠른 탐색이 보장된다. 하지만 힙은 노드를 다르게 정렬하기 때문에 이진 탐색을 사용할 수 없고, 트리의 모든 노드를 확인해야 한다.

다시 예시 힙을 살펴보자:

노드 (1)의 인덱스를 찾고 싶다면, 배열 [ 10, 7, 2, 5, 1 ]을 선형 탐색으로 순회하면 된다.

힙 속성은 탐색을 염두에 두고 설계된 것은 아니지만, 이를 활용할 수 있다. 최대 힙에서는 부모 노드가 항상 자식 노드보다 크다는 사실을 알고 있다. 따라서 찾고 있는 값보다 부모 노드가 작다면, 그 자식 노드(그리고 그 자식의 자식 노드 등)는 확인할 필요가 없다.

힙에 값 8이 있는지 확인해보자(실제로는 없다). 루트 노드 (10)부터 시작한다. 찾는 값이 아니므로, 왼쪽과 오른쪽 자식 노드를 재귀적으로 확인한다. 왼쪽 자식은 (7)이다. 이 값도 찾는 값이 아니지만, 최대 힙이기 때문에 (7)의 자식 노드를 확인할 필요가 없다. 그 자식들은 항상 7보다 작기 때문에 8이 될 수 없다. 오른쪽 자식 (2)도 마찬가지다.

이 작은 최적화에도 불구하고, 탐색은 여전히 O(n) 연산이다.

참고: 노드 값을 인덱스에 매핑하는 추가적인 딕셔너리를 유지하면 탐색을 O(1) 연산으로 만들 수 있다. 힙 기반의 우선순위 큐에서 replace()를 자주 호출해 객체의 "우선순위"를 변경해야 한다면, 이 방법을 고려해볼 만하다.

코드 살펴보기

이 개념들을 Swift로 구현한 내용은 Heap.swift에서 확인할 수 있다. 대부분의 코드는 직관적이다. 유일하게 복잡한 부분은 shiftUp()과 shiftDown()에 있다.

힙에는 두 가지 타입이 있다는 것을 이미 알 것이다: 최대 힙(max-heap)과 최소 힙(min-heap). 이 둘의 차이는 노드를 어떻게 정렬하느냐에 있다. 최대 힙은 가장 큰 값을 우선으로, 최소 힙은 가장 작은 값을 우선으로 한다.

MaxHeap과 MinHeap 두 가지 버전을 따로 만드는 대신, 하나의 Heap 객체를 만들고 isOrderedBefore 클로저를 사용한다. 이 클로저는 두 값의 순서를 결정하는 로직을 담고 있다. Swift의 sort()가 동작하는 방식과 유사하므로 익숙할 것이다.

정수형 최대 힙을 만들려면 다음과 같이 작성한다:

var maxHeap = Heap<Int>(sort: >)

최소 힙을 만들려면 다음과 같이 작성한다:

var minHeap = Heap<Int>(sort: <)

대부분의 힙 구현체가 <와 > 연산자를 사용해 값을 비교하는 반면, 이 구현체는 isOrderedBefore() 클로저를 사용한다는 점을 강조하고 싶었다.

함께 보기

위키백과의 힙(Heap) 항목

Swift 알고리즘 클럽을 위해 Kevin Randrup과 Matthijs Hollemans가 작성함