코딩고치

힙 힙은 데이터에서 최댓값과 최솟값을 빠르게 찾기 위한 완전 이진트리 (Complete Binary Tree)이다. 힙을 사용하는 이유 우선순위 큐와 같이 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 구현에 사용된다. 이진트리의 경우 한번 연산이 진행되면 데이터가 1/2가 되므로 시간 복잡도가 O($log {n}$)이 걸린다. 따라서 힙도 O($log {n}$)이 걸린다 (배열의 경우 최악의 경우에 O(n)이 걸림). 힙의 구조 최댓값을 구하는 최대 힙 (Max Heap)과 최솟값을 구하는 최소 힙 (Min Heap)으로 구분된다. 최대 힙 : 각 노드의 값은 자식 노드의 값보다 크거나 같다 (가장 위가 가장 큰 값). 최소 힙 : 각 노드의 값은 자식 노드의 값보다 작거나 같다 (가장 위가 가장 ..