힙

정의

이진 트리 형태를 가지며 우선순위가 높은 요소가 먼저 나가기 위해

요소가 삽입, 삭제될 때 바로 정렬되는 특징이 있음

---

특징

• 우선순위가 높은 요소가 먼저 나가는 특징을 가짐
  => 우선순위가 높은 요소를 루트로 배치하고 루트가 가장 먼저 나감
• 루트가 가장 큰 값이 되는 최대 힙(Max Heap)과 루트가 가장 작은 값이 되는 최소 힙(Min Heap)이 있음
  => 오름차순/내림차순 차이
• 자바스크립트에선 직접 구현해서 사용해야 함
• 힙은 추가/삭제가 핵심 로
• 우선순위 큐와 비슷하지만 우선순위 큐는 큐를 활용한 개념이기 때문에 같은 것은 아니며
  힙이 우선순위 큐보다 효율성이 높은 편

---

힙 요소 추가 알고리즘

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

---

힙 요소 제거 알고리즘

1. 요소 제거는 루트 정점만 가능
2. 루트 정점이 제거된 후 가장 마지막 정점이 루트에 위치
3. 루트 정점의 두 자식 정점 중 더 우선순위가 높은 정점과 바꿈
4. 두 자식 정점이 우선순위가 더 낮을 때까지 반복
5. 완전 이진 트리의 높이는 log N 이기 때문에 힙의 요소 제거 알고리즘은 O(log N) 시간복잡도를 가짐