Heap

Heap

• Heap은 완전 이진트리를 기반으로 한다.
• 최대 힙(Max Heap)은 루트 노드로 올라갈수록 저장된 값이 커지는 구조이다.
• 최소 힙(Min Heap)은 루트 노드로 올라갈수록 저장된 값이 작아지는 구조이다.
• 최대 힙이든 최소 힙이든 모든 부모 노드의 우선순위는 자식 노드보다 크거나 같다.
• 구현의 용이함을 위해 root index는 1부터 시작한다.
• 위 조건을 만족하며 완전이진트리 형태로 채워나가면 된다. 즉, 형제노드간 우선순위는 고려하지 않아도 된다.

Heap의 부모 노드와 자식 노드간 관계

• 부모 노드의 index = (왼쪽 자식 index) / 2
• 왼쪽 자식 index = (부모 index) * 2
• 오른쪽 자식 index = (부모 index) * 2 + 1

새로운 노드 추가 시

• 새로운 노드를 힙의 마지막 노드에 삽입한다. (우선순위를 제일 낮게)
• 부모 노드들과 우선순위를 비교하며 교환 반복.

노드 삭제 시

• 루트 노드를 삭제한다. (우선순위가 제일 높기 때문)
• 삭제된 자리로 Heap의 마지막 노드를 가져온다.
• 자식 노드들 중 더 우선순위가 높은 자식노드와 교환하며 이를 반복해 Heap을 재구성한다.
• Heap은 Priority Queue를 구현하는데 사용된다.
  • Priority Queue를 배열이나 연결리스트로 구현하게 되면 삭제 시 시간복잡도 O(1), 삽입 시 시간복잡도가 O(n)이 된다.
  • 반면 Heap을 이용해 구현할 경우 부모-자식간의 비교만 진행되기 때문에 삭제 시 시간복잡도 O(log2n), 삽입 시 시간복잡도 O(log2n)이 된다.
  • 따라서 삽입과 삭제의 편차가 덜한 Heap으로 구현.
• Java의 Priority Queue는 기본적으로 부모 노드의 key 값이 자식 노드의 key 값보다 작거나 같은 최소 힙(Min Heap)을 사용한다. (작을수록 우선순위가 높다)