[2. 트리, 힙, 그래프] 힙

힙(Heap)

힙의 특징은 다음과 같다.

- 최대 원소에 즉각적으로 접근할 수 있다. O(1)

- 원소 삽입과 삭제에 대해 O(logN)의 시간복잡도를 만족한다.

이러한 특징을 만족하기 위해 완전이진트리(Complete Binary Tree)를 이용한다.

* 완전 이진트리: 마지막 레벨의 노드를 제외하고는 모두 두 개의 자식이 있고, 마지막 레벨에서는 왼쪽부터 차례대로 노드 존재

위와 같은 완전 이진 트리 표현은 다른 노드를 가리키는 포인터를 저장할 필요가 없다.

그렇기 때문에 메모리 사용 측면에서 효율적이다.

 

부모노드에서 자식노드로 이동하는 것은 배열의 인덱스 계산으로 쉽게 이루어진다.

예를 들어, 부모 노드의 인덱스가 i라면, 자식 노드의 인덱스는 2 * i + 1, 2 * i + 2이다.

반대로 자식 노드의 인덱스가 i라면, 부모 노드의 인덱스는 (i - 1) / 2로 표현할 수 있다.

 

최대 힙과 최소 힙

최대 원소가 트리의 루트에 있도록 설정한 힙 -> 최대 힙

최소 원소가 트리의 루트에 있도록 설정한 힙 -> 최소 힙

 

최대 힙과 최소 힙을 유지하기 위해서 원소를 삽입하거나 삭제할 때 힙의 불변성을 유지해야 한다.

 

힙 연산 (원소 삽입)

원소 삽입 시에 가장 중요한 불변성은 완전 이진 트리를 유지하는 것이다.

이를 위해 배열의 맨 마지막 위치에 원소를 추가하는데,

마지막 레벨의 마지막 노드 바로 오른쪽에 새로운 노드를 추가하거나, 새로운 레벨을 추가하여 노드를 추가할 수 있다.

 

두 번째 조건은 모든 노드는 자식 노드보다 큰 값을 가지고 있어야 한다는 것이다.

힙의 가장 마지막 위치에 원소를 삽입하게 되면, 위 조건이 맞지 않는 경우가 생길 수 있다.

그럴 때에는 새로 삽입한 원소의 부모 노드와 값을 비교하고, 부모 노드보다 해당 노드가 더 크면 서로 Swap 하는 방식으로 삽입 연산을 수행한다.

완전 이진 트리의 높이는 최대 logN이므로, 삽입 연산의 시간 복잡도는 O(logN)으로 표현할 수 있다.

 

힙 연산 (원소 삭제)

힙에서는 항상 가장 큰 원소만 삭제할 수 있다.

힙의 최대 원소는 루트 노드에 존재하므로, 루트 노드를 삭제해야 한다.

이를 수행하기 위해 루트 노드와 힙의 마지막 노드를 교환한 후, 루트 노드를 삭제한다.

이렇게 하면 부모 노드가 자식 노드보다 큰 값을 만족하지 않을 수 있다.

그렇기 때문에 루트노드와 두 자식노드를 서로 비교하여 그 중 더 큰 노드와 교환한다.

이를 반복해서 수행하면서 힙의 조건을 만족하도록 연산을 수행한다.

 

힙 초기화하기

불변성을 유지하면서 힙을 초기화하는 가장 쉬운 방법은 비어있는 힙에 원소를 하나씩 추가하는 것이다.

그러나 이 방법은 O(NlogN)의 시간복잡도를 가지며 그렇게 효율적인 방법은 아니다.

 

힙 생성 알고리즘을 사용하면 이를 O(N) 시간에 초기화할 수 있다.

전체 트리의 아래쪽 서브 트리부터 힙 불변성을 만족하도록 힙을 업데이트하는 방법이다.

C++에서는 배열 또는 벡터의 반복자를 입력으로 받아 힙을 구성하는 std::make_heap() 함수를 제공하기도 한다.