지난 글: [알고리즘] - 해시 테이블
힙(heap)은 그래프의 트리 구조 중 하나로, '우선순위 큐(priority queue)'를 구현할 때 사용된다. 우선순위 큐는 데이터 구조의 하나로서 데이터를 자유롭게 추가할 수 있다. 반면, 데이터를 추출할 때는 최솟값부터 순서대로 선택된다. 추가는 자유롭게 하고 추출할 대는 작은 값부터 꺼내는 것이 우선순위 큐이다. 또, 힙을 표현하는 트리 구조에서는 각 정점을 '노드(node)'라고 부른다. 힙에서는 각 노드에 데이터가 저장된다.
1
1, 3, 6, 4, 8, 7 순서대로 각 노드에 숫자가 적혀 있다. 적혀 있는 숫자가 저장돼 있는 데이터이다. 이 노드들은 최대 두 개의 자식 노드를 갖는다. 또, 트리 모양은 데이터 개수에 의해 정해진다. 노드는 위에서부터 채워지며, 같은 층(단)에서는 왼쪽부터 채워진다.
1
/ \
3 6
/ \ \
4 8 7
2
또, 힙에서는 데이터 저장 위치를 정하기 위해 자식 노드의 숫자는 반드시 부모의 숫자보다 커야 한다는 규칙이 있다. 따라서 가장 위(뿌리)에 가장 작은 숫자가 적혀있다. 데이터를 추가할 때는 이 규칙을 지키기 위해 가장 아래층에 있는 왼쪽 노드부터 값을 채운다. 가장 아래 층이 모두 채워지면 새로운 층을 만들어서 가장 왼쪽부터 채운다.
3
힙에 숫자 5를 추가하는 경우를 보자. 추가되는 수는 먼저 2에서 설명한 위치에 저장된다. 가장 아래층에 한 자리가 남았으므로 거기에 저장된다.
1
/ \
3 6
/\ /\
4 8 7 5
4
부모의 숫자가 클 때는 조건을 만족하지 않으므로 부모와 자식을 교환한다.
1
/ \
3 5
/\ /\
4 8 7 6
5
부모6 > 자식5이므로 숫자를 교환했다. 이런 처리를 교환이 발생하지 않을 때까지 반복한다. 이번에는 부모1 < 자식5므로 교환이 발생하지 않는다. 이것으로 힙에 숫자 추가가 완료된다.
6
힙에서 숫자를 꺼낼 때는 가장 위에 있는 숫자가 추출된다. 힙에서는 가장 위에 있는 숫자가 최솟값을 지니고 있기 때문이다.
7
가장 위에 있는 숫자가 없어졌으므로 힙의 구조를 다시 정리해야 한다.
/ \
3 5
/\ /\
4 8 7 6
8
1에서 설명한 순서대로 가장 후미에 있는(여기서는 6) 숫자를 가장 위로 이동한다.
6
/ \
3 5
/\ /
4 8 7
9
부모 숫자보다 자식 숫자가 작은 경우는 자식의 좌우에 있는 숫자 중 더 작은 쪽과 교환한다(여기서는 3). 부모6 > 자식(우)5 > 자식(좌)3이므로 가장 왼쪽 자식과 부모를 교환한다. 이 처리를 교환이 발생하지 않을 때까지 반복한다.
3
/ \
6 5
/\ /
4 8 7
10
자식(우)8 > 부모6 > 자식(좌)4이므로 왼쪽 자식과 부모를 교환한다.
3
/ \
4 5
/\ /
6 8 7
11
이것으로 숫자 추출 처리가 완료되었다.
힙은 항상 가장 위에 최솟값이 있으므로 데이터 수에 상관없이 o(1) 시간에 최솟값을 추출할 수 있다. 또, 추출한 후에 힙을 재구축할 때는 가장 후미에 있는 데이터를 가장 위로 가져온 후 자식과 비교해 가며 아래 방향으로 진행한다. 이 때문에 계산 시간은 트리의 높이와 비례하게 된다. 데이터 수를 n이라고 하면 힙 형성 조건에 따라 트리의 높이는 log2n이므로 재구축의 계산 시간은 o(log n)이 된다. 데이터 추가도 마찬가지로 가장 후미에 있는 데이터를 추가한 후 힙 조건을 만족할 때까지 부모 숫자와 비교하며 위족으로 진행하기에 트리의 높이에 비례한 O(log n) 시간이 걸린다.
log 나오는 것부터가 정이 안간다. 힙의 구조와 데이터 추가, 추출 방식은 이해가 되었는데 계산 시간을 구하는 것은 언제나 힘들다.
참고 서적:
