힙 초기화하기

이번에는 힙에서 중요한 연산 중 하나인 힙 초기화에 대해 알아보겠습니다. 벡터, 리스트, 덱과는 달리 힙은 불변성을 유지해야 하기 때문에 초기화가 간단하지 않습니다. 가장 간단한 해결책은 비어 있는 힙에 하나씩 원소를 삽입하는 것입니다. 그러나 이 작업은 O(N log N)의 시간 복잡도를 가지며 효율적이지 않습니다.

그러나 힙 생성 알고리즘(heapification algorithm)을 사용하면 O(N) 시간에 힙을 초기화할 수 있습니다. 이 알고리즘의 기본 개념은 매우 간단합니다. 전체 트리의 아래쪽 서브 트리부터 힙 불변 속성을 만족하도록 힙을 업데이트하는 방식입니다. 일단 맨 마지막 레벨은 자식 노드가 없으므로 이미 힙 속성을 만족한다고 간주합니다. 그리고 한 레벨씩 트리 위로 올라가면서 힙 속성을 만족하도록 트리를 업데이트합니다. 이 작업은 O(N)의 시간 복잡도를 갖습니다. 다행히 C++ 표준은 배열 또는 벡터의 반복자를 인자로 받아 힙을 구성하는 std::make_heap() 함수를 제공합니다.