자료구조 - 힙(heap)

힙(heap) : 데이터에서 최대값과 최소값을  빠르게 찾기 위해 고안된 완전 이전 트리

                     ※ 완전 이전 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리

• 힙을 사용하는 이유
  • 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n) 이 걸림
  • 이에 반해, 힙에 데이터를 넣고, 최대값과 최소값을 찾으면, 𝑂(𝑙𝑜𝑔𝑛)이 걸림
  • 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨

□ 힙의 구조

• 힙은 최대값을 구하기 위한 구조 (최대 힙, Max Heap) 와, 최소값을 구하기 위한 구조 (최소 힙, Min Heap) 로 분류할 수 있음
• 힙은 다음과 같이 두 가지 조건을 가지고 있는 자료구조임
  1. 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우)
     • 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 작음
  2. 완전 이진 트리 형태를 가짐

□ 힙에 데이터 삽입하기 - 기본동작

 

□ 힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)

 

□ 힙에 데이터 삽입하기 - 삽입할 데이터가 힙의 데이터보다 클 경우(Max Heap의 예)

□ 힙의 구현

• 일반적으로 힙 구현시 배열 자료구조를 활용함
• 배열은 인덱스가 0번부터 시작하지만, 힙 구현의 편의를 위해, root 노드 인덱스 번호를 1로 지정하면, 구현이 좀더 수월함
  • 부모 노드 인덱스 번호 (parent node's index) = 자식 노드 인덱스 번호 (child node's index) // 2
  • 왼쪽 자식 노드 인덱스 번호 (left child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2
  • 오른쪽 자식 노드 인덱스 번호 (right child node's index) = 부모 노드 인덱스 번호 (parent node's index) * 2 + 1

□ 힙(heap) 시간 복잡도

• depth (트리의 높이) 를 h라고 표기한다면,
• n개의 노드를 가지는 heap 에 데이터 삽입 또는 삭제시, 최악의 경우 root 노드에서 leaf 노드까지 비교해야 하므로 ℎ=𝑙𝑜𝑔2𝑛ℎ 에 가까우므로, 시간 복잡도는 𝑂(𝑙𝑜𝑔𝑛)
  • 참고: 빅오 표기법에서 𝑙𝑜𝑔𝑛 에서의 log의 밑은 10이 아니라, 2입니다.
  • 한번 실행시마다, 50%의 실행할 수도 있는 명령을 제거한다는 의미. 즉 50%의 실행시간을 단축시킬 수 있다는 것을 의미함