이진 힙은 완전 이진 트리의 모양과 힙의 우선순위 조건을 함께 유지하는 자료구조이다. 보통 배열로 저장한다.
원리
0부터 세는 배열에서 인덱스 i의 자식은 2i+1, 2i+2에 놓인다. 삽입은 위로, 루트 제거는 아래로 원소를 이동하며 조건을 복구한다.
예시
최소 힙에서 가장 작은 값 제거는 마지막 원소를 루트로 옮긴 뒤 더 작은 자식과 교환하는 방식으로 구현할 수 있다. 높이가 로그 규모라 O(log n)에 처리한다.
주의할 점
루트 확인은 O(1), 삽입과 제거는 O(log n)이다. 전체 배열에서 아래쪽부터 정리하는 힙 구성은 O(n)이며, 원소를 하나씩 삽입하는 분석과 구별한다.