힙에서 가장 중요한 연산은 최대값 또는 최소값 반환(top 또는 peek), 요소의 삽입(push), 뿌리 노드 삭제(pop), 뿌리 노드 교체(replace)이다.
힙의 연산은 자식 노드와 부모 노드의 위치를 계산하는 것이 중요하다. 위 그림과 같이 배열로 힙을 나타내면 인덱스로 이러한 작업을 쉽게 수행할 수 있기 때문에 대개 힙 구현을 위한 자료구조로 연결 리스트보단 배열이 선호된다.
힙의 구현을 위해선 정적 배열 보다는 요소의 삽입과 삭제에 대응하여 용량을 조절할 수 있는 동적 배열이 적합하며 대개 배열의 현재 크기(size, 배열에 있는 요소의 개수)와 용량(capacity)을 관리하는 변수를 활용한다.
힙의 뿌리 노드는 배열의 맨 앞에 위치하며 자식 노드는 바로 다음 위치에 오는 식으로 배치된다.
힙에서 최대값 또는 최소값을 반환하는 연산은 배열의 첫 요소에 접근하는 것과 같으므로 시간 복잡도는 항상 이 된다.
힙에서 요소를 삽입하는 과정은 다음과 같다. 시간 복잡도는 이다.
힙의 뿌리 노드를 삭제하는 과정은 다음과 같다. 시간 복잡도는 이다.
힙 구현에 사용되는 배열의 0번 인덱스를 사용하지 않고 1번 부터 사용하는 경우의 인덱스 계산법은 다음과 같다.
왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2
오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
자식 노드의 인덱스 / 2 = 부모 노드의 인덱스
0번 인덱스를 사용할 경우엔 다음과 같다.
왼쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 1
오른쪽 자식 노드의 인덱스 = 부모 노드의 인덱스 * 2 + 2
(자식 노드의 인덱스 - 1) / 2 = 부모 노드의 인덱스
뿌리 노드 교체는 뿌리 노드를 삭제하면서 새로운 노드를 삽입하는 연산이다. 삭제 후 삽입하는 연산과 결과는 같지만 힙의 특성상 두 연산을 한번에 진행하면 연산과정을 한번만 수행하면 되기 때문에 따로 하는 것보다 더 효율적이다.
<algorithm>
헤더에서 힙을 위한 기능을 제공한다.std::vector
를 사용한다.std::make_heap()
을 사용한다. 비교 방법을 지정하지 않으면 기본적으로 최대 힙이 되며 최소 힙으로 만들 수도 있다.std::push_heap()
, std::pop_heap()
이 있다.heapq
가 있다. 이 모듈을 사용하려면 import
해야한다.heapq.heapify(list)
을 사용하면 리스트의 모든 요소가 최소 힙 배열의 순서대로 재구성된다.heapq.heappush(heap, item)
와 heapq.heappop(heap)
함수를 제공한다.heapq.heappushpop(heap, item)
함수는 힙에 item을 push한 다음, 가장 작은 요소를 pop하고 반환한다. 이 함수는 heappush()
를 호출하고 heappop()
를 호출하는 것보다 더 효율적이다.heapq.heapreplace(heap, item)
함수는 위와 반대로 가장 작은 요소를 pop하고 반환한 후에 item을 push하는 함수이다. 이 함수도 heappop()
한 다음 heappush()
하는 것보다 더 효율적이다.heapq._heapify_max(list)
함수는 리스트를 최대 힙으로 변환해준다.heapq._heappop_max(heap)
함수가 있지만 최대 힙의 push연산을 위한 함수는 없다.heappush
할때 삽입할 값을 음수로 변환하여 삽입하고, heappop
으로 추출된 값을 다시 음수로 변환하여 원래 값이 나오게 만들면 최소 힙을 마치 최대 힙 같이 활용할 수 있다.