힙 (Heap)

힙 (Heap)

완전 이진 트리 기반 반정렬 자료구조로, 부모가 자식보다 크거나(최대힙) 작은(최소힙) 값을 가짐

특징: 부모-자식만 정렬(형제 간 순서 없음), 배열 구현, 우선순위 큐 최적

종류: 최대 힙(부모≥자식, 루트=최대) / 최소 힙(부모≤자식, 루트=최소)

배열 구현: 왼쪽자식=2i+1, 오른쪽자식=2i+2, 부모=⌊(i-1)/2⌋

연산

• •삽입(Insert): 끝에 추가 → Heapify-Up(부모와 비교/교환 반복), O(log n)
• •추출(Extract): 루트 제거 → 마지막→루트 → Heapify-Down(자식과 비교/교환), O(log n)
• •조회(Peek): 루트 반환, O(1)
• •Heapify: Bottom-Up으로 배열→힙, O(n) (대부분 노드가 낮은 높이)

시간 복잡도: 삽입·삭제 O(log n), 조회 O(1), 힙 생성 O(n)

장점: 최대/최소 O(1) 접근, 삽입·삭제 효율, 배열 기반 캐시 효율

단점: 검색 O(n), 정렬 불완전, 중간 요소 접근 어려움

적용사례: 우선순위 큐, Heap Sort, 다익스트라, A*, 중앙값 유지(두 힙)

비교: 힙(부분정렬/O(log n)) vs BST(완전정렬/평균 O(log n))

연관: 우선순위 큐, Heap Sort, 완전 이진 트리, Heapify