힙(Heap) 자료구조

Q. 힙(Heap)자료구조에 대해서 설명해주세요

A. 힙(Heap)은 완전 이진 트리 형태를 갖춘 자료구조로, 우선순위 큐를 구현하는 데 주로 사용됩니다. 힙은 보통 두 가지 종류가 있습니다.

• 최대 힙 (Max Heap): 부모 노드가 자식 노드보다 항상 크거나 같도록 구성된 트리입니다. 루트 노드에는 가장 큰 값이 위치합니다.

• 최소 힙 (Min Heap): 부모 노드가 자식 노드보다 항상 작거나 같도록 구성된 트리입니다. 루트 노드에는 가장 작은 값이 위치합니다. 힙은 삽입과 삭제 연산 시 시간 복잡도가 O(lon n)으로 효율적이며, 정렬, 우선순위 큐 등의 알고리즘에서 활용됩니다. 일반적으로 배열을 사용해 구현하며, 배열의 인덱스를 통해 부모-자식 관계를 쉽게 찾을 수 있습니다.

---

Q. 힙의 삽입 연산의 시간 복잡도가 log n 이라고 하셨는데, 어떻게 log n 이 나오는지 설명해주실 수 있나요?

A. 삽입 과정에서 힙은 트리의 가장 마지막 자리에 새로운 노드를 넣습니다. 이런 삽입 자체는 O(1)의 시간이 걸립니다. 그후 새로 삽입된 노드가 최대 힙 또는 최소 힙을 만족하지 않으면 부모 노드와 비교해 자리를 교환하는 과정을 반복합니다. 이 과정을 상향 이동(upheap, or bubble-up) 이라고 부르며, 교환할 떄마다 한 레벨 위로 올라갑니다. 힙의 높이는 log n에 비례하므로, 상향 이동하는 최대 횟수는 트리의 높이만큼 발생할 수 있습니다. 결국 상향 이동은 트리의 높이에 따라 최대 O(log n)의 시간이 걸립니다.

---

Q. 힙의 높이가 왜 log n의 비례하죠?

A. 힙의 높이가 log n인 이유는 힙이 완전 이진 트리의 구조를 가지기 때문입니다. 완전 이진 트리는 트리의 각 레벨이 모두 채워져 있으며, 마지막 레벨은 왼쪽부터 차례대로 채워지는 이진 트리입니다. 이 구조는 트리의 높이가 노드 수와 특정한 관계를 가집니다. 이진 트리는 각 부모 노드가 최대 두 개의 자식을 가집니다. 즉, 루트에서부터 자식으로 내려갈수록 트리의 노드 수는 2의 제곱의 수 만큼 증가합니다. 예를 들어, 레벨 0의 1개의 노드, 레벨 1의 2개의 노드, 레벨 2의 4개의 노드, 레벨 3의 8개의 노드... 그렇다면 높이가 h인 완전 이진 트리에서 총 노드의 수 n은 등비 수열의 합이므로 2^(h+1) - 1 이 됩니다. 이때 h가 트리의 높이 이므로 h는 log n의 근사값이 됩니다.