부모의 값이 자식의 값 이상(최대 힙) 또는 이하(최소 힙)가 되도록 값을 배치한 완전 이진 트리. 배열로 나타낼 수 있으며, 루트를 a[0]으로 하면 a[i]의 자식은 a[2i+1]과 a[2i+2]. 최댓값(최솟값)의 참조가 O(1), 추가와 꺼내기가 O(log n)이며, 우선순위 큐나 힙 정렬에 쓰인다.
일본어 명칭: 二分ヒープ
이진 힙(Binary Heap)은(는) 자료 구조와 알고리즘 등 1개 분야의 연습 문제 3개에 나와요.
분야: 자료 구조와 알고리즘
정답: A. 자식은 a[9]와 a[10], 부모는 a[1]
루트를 a[0]으로 하는 경우, a[i]의 자식은 a[2i+1]과 a[2i+2], 부모는 a[(i−1)÷2의 버림]입니다. i = 4이면 자식은 a[9]와 a[10], 부모는 a[(4−1)÷2] = a[1]입니다. 루트를 a[1]로 하는 경우는 자식이 a[2i]와 a[2i+1], 부모가 a[i÷2]가 되므로, 어느 방식인지 확인하는 것이 중요합니다. 이처럼 힙은 완전 이진 트리이므로 포인터를 쓰지 않고 배열로 나타낼 수 있으며, 첨자 계산만으로 부모와 자식을 따라갈 수 있습니다.
힙 정렬은 배열 안에 이진 힙을 만들고, 루트의 최댓값을 맨 끝과 교환하여 힙을 줄이는 것을 반복하므로 최악에도 O(n log n)이며, 추가 영역은 상수로 충분합니다.
최악의 경우에도 시간 복잡도가 O(n log n)이고, 작업용 배열 등의 추가 기억 영역을 거의 사용하지 …이 성질 때문에 이진 힙은 우선순위 큐의 구현에 자주 쓰입니다.
부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50,…배열(Array) 포인터(Pointer) 시간 복잡도(Time Complexity) 깊이 우선 탐색(Depth-First Search) 너비 우선 탐색(Breadth-First Search) 다익스트라 알고리즘(Dijkstra's Algorithm) 동적 계획법(Dynamic Programming) 스택(Stack) 안정 정렬(Stable Sort) 연결 리스트(Linked List)