Heap 자료구조 완벽 정리: 우선순위 큐의 핵심

1. Heap이란?

최댓값이나 최솟값을 $O(\log N)$만에 찾아내고 삭제/삽입하기 위해 고안된 완전 이진 트리(Complete Binary Tree) 기반의 자료구조다.

---

2. 핵심 속성

1. 구조적 속성: 마지막 레벨을 제외하고 모든 레벨이 꽉 채워져 있어야 하며, 왼쪽부터 채워진다. (배열로 구현하기 좋음)
2. 순서 속성: 부모 노드는 자식 노드보다 항상 우선순위가 높다 (Max Heap의 경우 부모 $\ge$ 자식).

---

3. 연산 과정

• 삽입 (Push): 맨 끝에 넣고, 부모와 비교하며 올라간다 (Percolate Up).
• 삭제 (Pop): 루트를 빼고, 맨 끝 원소를 루트로 올린 뒤, 자식과 비교하며 내려간다 (Percolate Down).

이 구조 덕분에 항상 트리의 높이만큼만 비교하면 되므로 효율적이다. Dijkstra, Prim 알고리즘 등의 기반이 된다.