힙(heap) 자료구조에 대해 토론하기

[ChanhuiSeok]

자료구조 중에서 힙(heap) 이라는 것이 존재합니다.
각종 시험이나 면접 질문에서 힙에 대한 질문이 단골로 등장하기도 하는데요!
힙과 관련하여 댓글에 누구나 자유롭게 작성하실 주제는 다음과 같습니다.

• 힙은 완전 이진트리입니다. 완전 이진트리가 무엇일까요? 자유롭게 작성해 주시면 감사하겠습니다.
• 힙을 사용하는 이유가 무엇일까요? 힙이 사용된 예시가 있을까요?
• 힙과 관련된 시간복잡도에 대해 자유롭게 작성해 주시면 감사하겠습니다. (예 : 삽입 및 삭제, heapify, 힙 정렬 등)

[ChanhuiSeok]

• 완전 이진 트리 : 루트부터 차례대로 노드가 모두 채워진 이진 트리인데, 마지막 레벨에는 전부 채워질 필요는 없으며 왼쪽부터 채워지는 형태입니다.
• 힙은 최댓값 혹은 최솟값을(각각 max heap, min heap 일 경우) 찾는 데에 걸리는 시간복잡도가 O(logN)이라고 할 수 있습니다. 그래서 이 점에서 유용할 것 같고, 우선순위 큐 구현에 힙을 사용한다면 가장 우선순위가 높은 데이터부터 빠져나오는 것을 쉽게 구현할 수 있습니다.
• 힙은 완전 이진 트리라서 삽입과 삭제 시간복잡도는 트리의 높이 logN 에 따른다고 볼 수 있습니다. 힙에 새로운 노드가 추가되거나, 어떤 노드를 삭제하게 되면 다시 전체적으로 힙 구조(최대 혹은 최소 힙)를 유지시켜야 하는데 그 과정을 heapify 라고 하며 시간 복잡도는 O(logN) 입니다.

[jjangsungwon]

좋은 질문 감사드립니다.

• 완전 이진 트리는 마지막 레벨을 제외한 모든 레벨의 노드가 모두 채워져 있으며 마지막 레벨의 노드들은 왼쪽부터 채워지는 형태의 트리로 알고 있습니다.
• 힙 자료구조는 최댓값 혹은 최솟값을 찾는 작업을 효율적으로 수행하는 자료구조입니다. 트리의 균형이 잡혀 있다면 시간 복잡도 O(logN)으로 최댓값 혹은 최솟값을 찾을 수 있습니다. 따라서 이 부분을 활용할 수 있는 다양한 실생활에서 활용되고 있습니다. 대표적으로 실시간 급상승 검색어 제공 서비스가 있습니다.
• 힙의 삽입과 삭제는 모두 시간 복잡도 O(logn)입니다. 힙의 삽입은 새로운 요소를 힙의 마지막 노드에 삽입한 후 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킵니다. 힙의 삭제는 루트 노드를 삭제한 후 삭제된 루트 노드에 힙의 마지막 노드를 가져와서 힙을 재구성합니다. 삽입과 삭제에서 힙을 재구성하는 과정을 heapify라고 하며 시간 복잡도는 O(logN) 입니다. 추가적으로 힙이 균형이 깨지면 위에서 언급한 시간 복잡도보다 오래 걸릴 수 있습니다. 이를 방지하기 위해서 Red Black Tree 등의 대안이 있습니다.