• Heap 은 완전 이진 트리의 일종으로, 부모 노드와 자식 노드 간의 특정한 조건을 만족하는 자료구조를 말합니다.

• 여기서 완전 이진 트리란 부모 노드 밑에 자식 노드가 최대 2개 까지 있을 수 있으며, 마지막 레벨을 제외한 모든 레벨의 노드가 완전히 채워져 있는 트리 구조 입니다.

  Tree

Heap 종류 ( Max Heap, Min Heap )

Heap 구현 방법

• Heap 이 동작하는 방식을 보고 시간 복잡도를 확인해보자.
  • Heap 이 재배열 할 때 heapify() 연산은 O ( log n ) 의 시간 복잡도를 가집니다.
  • 이유는 heapify() 가 Heap 의 높이 만큼 재귀 호출을 하기 떄문 입니다. 예를 들어, 자식 노드가 최대 2개인 Heap 에서 전체 노드의 개수가 n 이고, h 가 Heap 의 높이라면 n : 4 → h : 2 되고, n : 8 → h : 3 이 됩니다.
  • 즉, 이를 계산식으로 표현하면 높이 h = log2^n 이 됩니다.

문제연습