[자료구조] 힙

힙(Heap)이란?

 

완전 이진 트리 형태로 구성된 자료구조이며, 특정 조건(힙 속성)을 만족하도록 정렬된 트리이다.

힙은 우선순위 큐(Priority Queue)와 같은 문제를 효율적으로 해결할 때 유용하다.

---

힙 속성(Heap Property)

1. 최대 힙(Max-Heap)
2. 최소 힙(Min-Heap)

최대 힙(Max-Heap)

• 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같음.
• 루트 노드가 가장 큰 값을 가짐.

최소 힙(Min-Heap)

• 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같음.
• 루트 노드가 가장 작은 값을 가짐.

 

---

힙 연산

1. 삽입(Insert)

• 새로운 노드를 힙의 마지막 위치에 삽입.
• 부모와 비교하며 힙 속성을 유지하도록 교환(상향 조정, upheap).

2. 삭제(Delete)

• 일반적으로 루트 노드(최댓값 또는 최솟값)를 제거.
• 힙의 마지막 노드를 루트로 옮기고, 자식들과 비교하며 힙 속성을 유지(하향 조정, downheap).

3. 힙 정렬(Heap Sort)

• 힙을 이용해 데이터를 정렬하는 알고리즘.
• 힙에 데이터를 삽입 후, 루트 노드를 제거하며 정렬.
• 루트 노드를 끝에 있는와 바꿔주고 끝에 있는 정보를 빼준다. 
• 힙 속성이 꺠져있다면 다시 힙속성을 지켜준다.
• 또 루트 노드를 끝에 있는 노드와 바꿔준다. (바꾸고 끝에 있는 숫자를 뒤로 뺌)

---

시간 복잡도

• 삽입: O(log ⁡n) (트리의 높이만큼 비교)
• 삭제: O(log⁡ n) (트리의 높이만큼 조정)
• 최대값/최솟값 조회: O(1) (루트 노드 직접 접근)