힙(Heap) 자료구조

힙(Heap)이란 ? 완전 이진 트리의 일종으로, 데이터에서 최댓값과 최솟값을 빠르게 찾기 위해 만들어진 자료구조입니다. 힙을 사용하는 이유는 최댓값과 최솟값을 찾기 위해 배열을 사용하는 경우 O(n)의 시간복잡도가 걸리는 반면, 힙을 사용하면 O(logn)의 시간복잡도가 소요되므로 시간적으로 효율적이기 때문입니다. 완전 이진 트리 (Complete Binary Tree)란 ? 이진 트리에 노드를 삽입할 때 왼쪽부터 차례대로 삽입하는 트리로 아래 그림과 같습니다. 만약, 왼쪽이 비어 있고 오른쪽이 채워져있다면 완전 이진 트리라고 할 수 없습니다. 힙의 특징 힙은 최대 힙과 최소 힙으로 나눠집니다. 최대 힙(max heap) : 부모 노드의 값이 자식 노드이 값보다 크거나 같은 완전 이진 트리. ( 부모 ..