힙

 

힙은 다음과 같은 시간 복잡도를 만족해야 한다.

 

• O(1) : 최대 원소에 즉각적으로 접근할 수 있어야 한다.
• O(log N) : 원소 삽입에 대한 시간 복잡도
• O(log N) : 최대 원소 삭제에 대한 시간 복잡도

 

원소 삽입 또는 삭제에 대하 O(log N)의 시간 복잡도를 만족하기 위해 트리 구조를 사용해야 한다.

이 경우 완전 이진 트리를 사용해야 한다.

완전 이진 트리는 마지막 레벨의 노드를 제외하고 모두 두 개의 자식 노드가 있고,

마지막 레벨에서는 왼쪽 부터 차례대로 노드가 있는 트리이다.

 

 

완전 이진 트리는 새로운 원소를 트리의 마지막 레벨에 추가하는 방식으로 구성할 수 있다.

만약 마지막 레벨의 모든 노드가 채워져 있다면 새로운 레벨을 하나 더 만들고,

맨 왼쪽에 위치에 노드를 추가한다.

완전 이진 트리는 트리의 데이터를 배열에 이용하여 저장할 수 있다.

 

즉, 루트 노드를 배열 또는 벡터의 맨 마지막에 저장하고,

그 다음 레벨의 모든 노드는 왼쪽부터 오른쪽 순서로 저장한다.

이러한 방식의 완전 이진 트리 표현은

다른 노드를 가리키는 포인터를 저장할 필요가 없기 때문에

메모리 사용 측면에서 효율적이다.

 

부모 노드로부터 자식 노드로 이동하는 것은 

단순히 배열의 인덱스 계산으로 가능하다.

 

만약 부모 노드가 i번째 배열 원소로 저장되어 있다면,

자식 노드는 2*i + 1 또는 2 * i + 2번째 인덱스로 접근하면 된다.

 

마찬가지로 자식 노드가 i번째 인데긋라면 부모 노드는 (i-2)/2 번째 인덱스이다.

 

힙 구성의 기본 원칙

 

이제 원소를 삽입하거나 삭제할 때 유지해야 할 힙의 불변성 또는 조건에 대해 알아보자.

첫 번째 조건은 최대 원소에 즉각적으로 접근 가능해야 한다는 점이다.

 

최소 힙과 최대 힙의 차이

 

이를 위해 최대 원소가 항상 고정된 위치에 있어야 한다.

힙을 구현할 때는 항상 최대 원소가 트리의 루트에 있도록 설정한다.

이를 위해 부모 노드가 두 자식 노드보다 항상 커야한다는 불변성을 유지해야 한다.

이렇게 구성한 힙을 최대 힙이라 한다.

 

최대 원소에 빠르게 접근할 수 있다면

반대로 최소 원소에 빠르게 접근할 수 있도록 힙을 구성할 수도 있다.

이러한 힙을 만들려면 앞서 말했던 모든 비교 연산을 반대로 설정하면 된다.

이렇게 구성한 힙을 최소 힙이라 한다.

 

힙 연산

 

힙에 원소 삽입하기

 

힙의 가장 중요한 불변성은 완전 이진 트리를 유지해야 한다는 점이다.

완전 이진 트리를 유지하고 있어야 배열 자료 구조를 이용하여 힙을 저장할 수 있다

완전 이진 트리를 유지하는 힙에 새 원소를 삽입하려면

단순히 배열의 맨 마지막 위치에 원소를 추가하면 된다.

 

이 작업은 기존 트리의 마지막 레벨,

마지막 노드 바로 오른쪽에 새로운 노드를 추가하는 것과 같다.

 

만약 마지막 레벨이 꽉 차있다면 새로운 레벨을 추가하여 노드를 추가한다.

 

이번에는 다른 불변 조건에 대해 생각해보자.

모든 노드는 자식 노드보다 더 큰 값을 가지고 있어야 한다.

일단 기존의 트리는 이미 이 불변 조건을 만족하고 있다고 가정하겠다.

 

그러나 새로운 원소를 트리의 맨 마지막 위치에 추가한 후에는

이 조건이 성립되지 않을 가능성이 생긴다.

 

이를 해결하기 위해 새로 삽입한 원소의 부모 노드와 값을 비교하고,

만약 부모 노드가 더 작으면 서로 교환한다.

만약 부모 노드에 다른 자식 노드가 있다 하더라도

이 자식 노드는 새로 추가한 원소보다 작다 (새 원소 > 부모 노드 > 자식 노드).

그러므로 새로 추가한 원소를 루트 노드로 간주하는 서브 트리는 힙 불변성을 만족하게 된다.

 

그러나 새 원소가 여전히 새 부모 노드보다 큰 값을 가질 수 있다.

따라서 전체 트리에서 불변 조건이 만족하도록 교환 작업을 반복해야 한다.

완전 이진 트리의 높이는 최대 log N이므로,

삽입 연산의 시간 복잡도는 O(log N)으로 표현할 수 있다.

 

 

11을 맨 마지막에 추가한 후에는 힙의 속성을 만족하지 못하게 된다.

그러므로 원소 10과 11을 서로 교환해야 한다.

이러한 동작을 여러 레벨에 걸처 수행하여 제 자리를 찾는 것이 힙의 원소의 추가 과정이다.

 

 

힙에서 원소 삭제하기

일단 힙에서는 가장 큰 원소만 삭제할 수 있다. 다른 원소에는 직접 접근할 수 없기 때문이다.

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

루트를 삭제할 경우, 어느 노드를 이용하여 루트를 대체할 것인지를 결정해야 한다.

이를 위해 먼저 루트 노드와 트리의 맨 마지막 노드를 서로 교환한 후, 마지막 노드를 삭제해야 한다.

 

이렇게 하면 최대 원소를 삭제한 것이 되며,

다만 루트 위치에서 부모 노드가 자식 노드보다 커야 한다는 불변성을 만족하기 못하게 된다.

이 문제를 해결하기 위해

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

 

이제 루트 노드의 두 서브 트리 중 하나에 대해서 불변 규칙이 깨진 상태가 되었을 것이다.

그러므로 서브 트리에 대해서도 노드 교환 작업을 재귀적으로 반복한다.

이러한 방식으로 불변성을 만족하지 못하는 위치가 점차 트리의 아라쪽으로 이동한다.

교환 작업의 최대 횟수는 트리의 높이와 같으므로 원소 삭제의 시간 복잡도는 O(log N)으로 표현할 수있다.

이러한 원소 삭제 과정은 다음과 같다.

 

 

 

힙 초기화하기

 

이번에는 힙에서 중요한 연산 중 하나인 힙 초기화에 대해 알아보겠다.

벡터, 리스트, 덱과는 다릴 힙은 불변성을 유지해야 하기 때문에 초기화가 간단하지 않았다.

가장 간단한 해겨책은 비어 있는 힙에 하나씩 원소를 삽입하는 것이다.

그러나 이 작업은 O(N log N)의 시간 복잡도를 가지며 효율적이지 않다.

 

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

이 알고리즘의 기본 개념은 매우 간단하다.

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

일단 맨 마지막 레벨은 자식 노드가 없으므로 이미 힙 속성을 만족한다고 간주한다.

 

그리고 한 레벨씩 트리 위로 올라가면서 힙 속성을 만족하도록 트리를 업데이트한다.

이 작업은 O(N)의 시간 복잡도를 가진다.

 

다행스럽게도 C++ 표준은 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 

std::make_haep()함수를 제공한다.