힙이란? 힙은 힙 속성을 충족하는 완전한 이진 트리 데이터 구조로 우선순위 큐를 위하여 만들어진 자료구조이다. 모든 노드에 대해 해당 하위 노드의 값은 자체 값보다 작거나 같으며, 힙은 가장 작은(또는 가장 큰) 요소가 항상 트리의 루트에 있는 우선순위 큐를 구현하는데 자주 사용된다. 최대 힙(Max Heap)과 최소 힙(Min Heap) 두 가지 종류가 있다. 힙의 종류 최대 힙(max heap) 루트 노드의 값은 모든 하위 노드 중에서 가장 커야하며 왼쪽 및 오른쪽 하위 트리에도 동일한 작업이 수행되야 한다. 최대 힙에 필요한 총 비교 횟수는 트리 높이에 따라 다른데 완전한 이진 트리의 높이는 항상 로그된다. 따라서 시간 복잡도도 O(logn)이다. key(부모노드) >- key(자식노드) 최소 힙(..
