Heap

• 이진 트리 형태를 가진다.
• 우선순위가 높은 요소가 먼저 나가기 위해 요소가 삽입, 삭제 될 때 바로 정렬되는 특징이 있다.
• 우선 순위가 높은 요소가 먼저 나가는 특징을 가진다.
• 2가지 종류
  1. 루트가 가장 큰 값이 되는 최대 힙(Max Heap)
  2. 루트가 가장 작은 값이 되는 최소 힙(Min Heap)
• 아쉽게도 자바스크립트에서는 직접 구현하여 사용해야 한다.

Heap 요소 추가 알고리즘

1. 요소가 추가 될 때는 트리의 가장 마지막에 정점에 위치한다.
2. 추가 후, 부모 정점보다 우선순위가 높다면 부모 정점과 순서를 바꾼다.
3. 과정을 반복하여, 가장 우선순위가 높은 정점이 루트가 된다.
4. 완전 이진 트리의 높이는 logN이기에 힙의 요소 추가 알고리즘은 O(logN)의 시간 복잡도를 가진다.

Heap 요소 제거 알고리즘

• 요소 제거는 루트 정점만 가능하다
• 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치한다.
• 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꾼다.
• 두 자식 정점이 우선순위가 더 낮을 때까지 반복한다.
• 완전 이직 트리의 높이는 longN이므로 힙의 요소 제거 알고리즘은 O(logN)의 시간 복잡도를 가진다.