힙(Heap)

---

<힙 노트 정리>

---

힙이란?

힙은, 우선 순위 큐(우선순위가 높은 순서대로 나가는 queue)의 대표적인 예시이며, 완전 이진 트리(최대 자식을 2개 가지는 이진 트리(binary tree)이면서, 맨 아랫 줄(레벨)을 제외한 부분은 전부 차 있는 트리)의 형태를 하고 있는 자료구조이다. 부모 노드보다 자식 노드가 더 커서 결국 루트 노드가 최솟값인 최소 힙 과, 반대로 부모 노드가 더 커서 루트 노드가 최댓값인 최대 힙으로 구분된다.

주요 연산과 시간 복잡도(최소 힙에서)

삽입 - 힙의 가장 아래에 데이터를 삽입하며, 이 때 부모 노드와 값을 비교해 자식 노드가 더 작으면 데이터를 서로 교체한다. 이를 힙의 규칙을 만족할 때 까지 반복한다.
삭제 - 맨 위(루트 노드의 데이터) 삭제 후 힙의 가장 마지막 노드를 루트로 가져온다. 이후 삽입 연산과 마찬가지로 자식 노드가 더 작으면 교체를 반복한다.

두 연산 전부 최악의 경우는 맨 아래까지 내려가는 경우이므로 시간복잡도는 $O(logN)$ 이다.

---

JAVA에서의 힙 사용

import java.util.PriorityQueue;