Heap

정의

완전 이진 트리 기반의 자료구조

종류

• Max Heap
  • root node의 값은 모든 하위 node 중에서 가장 큰 값을 가지며 모든 하위 트리에서도 동일한 원칙을 가져야 한다.
• Min Heap
  • root node의 값은 모든 하위 node 중에서 가장 작은 값을 가지며 모든 하위 트리에서도 동일한 원칙을 가져야 한다.

특징

• 완전 이진 트리
• root 값
  • 힙에서 root의 값은 항상 힙의 최대값이나 최소값으로 유지되는 특징을 가진다.
• 부모-자식 관계
  • 힙에서 부모 노드와 자식 노드 간 관계는 인덱스 i를 기준으로 왼쪽 노드는 2i+1, 오른쪽 노드는 2i+2의 공식을 가진다.
• 삽입/제거 효율성
  • 두 작업 모두 O(log n)의 시간복잡도를 가진다.
• heapify
  • 힙 구조를 유지하기 위해 element를 재배치하는 과정

힙 삽입/삭제 과정

• 삽입
  
  1. 새로운 값은 우측 하단의 빈 노드에 위치 시킨다.
  2. 부모 노드와 값을 비교해 위치를 결정한다.
  3. 위치가 바뀌지 않을 때 까지 2번을 반복한다.
• 삭제

1. root 값을 삭제하고 트리의 마지막 값을 root 노드로 이동시킨다.
2. root 값과 자식 노드의 값을 비교해 위치를 결정한다.
3. 위치가 바뀌지 않을 때 까지 2번을 반복한다.

장점

• min/max 값에 대한 빠른 접근 속도 O(1)
• 삽입/삭제 동작에 대한 효율성 O(log n)

참고자료

geeksforgeeks - heap