[자료 구조] 힙

힙(heap)은 그래프의 트리 구조 중 하나로, '우선순위 큐(priority queue)'를 구현할 때 사용됩니다. 우선순위 큐는 자료 구조의 하나로서 데이터를 자유롭게 추가할 수 있습니다. 반면, 데이터를 추출할 때는 최소값부터 순서대로 선택됩니다. 추가는 자유롭게 하고 추출할 때는 작은 값부터 꺼내는 것이 우선순위 큐입니다. 또한, 힙을 표현하는 트리 구조에서는 각 정점을 '노드(node)'라고 부릅니다. 힙에서는 각 노드에 데이터가 저장됩니다. - 책 알고리즘 도감

 

 

1. 기본 구조와 개념

이것은 힙의 한 예입니다. 힙의 각 노드에 적혀 있는 숫자가 저장돼 있는 데이터입니다. 이 노드들은 최대 두 개의 자식 노드를 가집니다. 그리고 트리의 모양은 데이터의 개수에 의해 정해집니다. 또, 노드는 위에서부터 채워지며, 같은 층(단)에서는 왼쪽부터 채워집니다.

 

또한, 힙에서는 데이터 저장 위치를 정하기 위해 자식 노드의 숫자는 반드시 부모의 숫자보다 커야 한다는 규칙이 있습니다. 따라서 가장 위(뿌리)에 가장 작은 숫자(1)가 들어있습니다.

 

 

 

2. 데이터 추가

힙에 숫자 5를 추가하는 경우를 보겠습니다.

일단, 남아있는 빈자리에 5를 넣습니다. 그런데, 힙에서는 자식 노드의 숫자가 부모 노드의 숫자보다 커야한다는 규칙이 있었죠? 그리고 추가된 5가 부모인 6보다 작으니까 서로 위치를 바꿉니다.

 

 

추가 완료

5와 6을 바꾼 뒤 5를 다시 부모와 비교해보지만 부모(1)보다는 크니까 여기서는 교환이 발생하지 않게 되고, 따라서 추가가 완료됩니다.

 

 

3. 데이터 추출

 

힙에서 숫자를 꺼낼 때는 가장 위에 있는 숫자(최소값)가 추출됩니다. 그리고 가장 위에 있는 숫자가 없어졌으므로 힙의 구조를 다시 정리해야 합니다.

 

 

먼저, 가장 후미에 있는 숫자(6)를 가장 위로 이동시킵니다.

 

 

 

 

부모 숫자보다 자식 숫자가 작은 경우는 자식의 좌우에 있는 숫자 중 더 작은 쪽과 교환합니다.

부모(6) >자식(우)(5) > 자식(좌)(3) 이므로 왼쪽 자식과 위치를 바꿉니다. 이 단계를 더 이상 교환이 생기지 않을 때까지 반복합니다.

 

 

추출 후 재구축 완료

 

 

<해설>

힙은 항상 가장 위에 최소값이 있으므로 데이터 수에 상관없이 O(1) 시간에 최소값을 추출할 수 있습니다. 또한, 추출한 후에 힙을 재구축할 때에는 가장 후미에 있는 데이터를 가장 위로 가져온 후 자식과 비교해 가며 아래 방향으로 진행합니다. 이 때문에 계산 시간은 트리의 높이와 비례하게 됩니다. 데이터 수를 n이라고 하면 힙 형성 조건에 따라 트리의 높이는 log2n이므로 재구축의 계산 시간은 O(log n)이 됩니다. 데이터 추가도 마찬가지 입니다. 가장 후미에 데이터를 추가한 후 힙 조건을 만족할 때까지 부모 숫자와 비교하며 위쪽으로 진행합니다. 따라서 트리의 높이에 비례한 O(log n) 시간이 걸립니다.

 

<활용 예>

관리하고 있는 데이터 중에서 최소값을 자주 추출해야 하는 경우에는 힙이 편리합니다. 예를 들어, 다익스트라 알고리즘에서는 후보가 되는 노드 중에서 최소값을 매 단계에서 선택하는데, 이 때 노드를 관리하기 위해 힙을 사용하는 경우도 있습니다.

 

참고 - 책 알고리즘 도감