Heap이란? 힙은 최댓값과 최솟값을 빠르게 찾기 위해 고안된 완전 이진 트리의 일종입니다. 완전이진트리란, 왼쪽부터 차례로 마지막 레벨의 노드를 제외한 모든 노드가 채워져있는 트리입니다. 최솟값이나 최댓값을 찾기 위해 배열은 O(n)의 시간이 걸리는 반면, 힙은 O(log2n)의 시간이 걸리기에 효율적입니다. 힙 자료구조는 우선순위 큐(Priority Queue)를 구현하기 위해 고안되었습니다. 힙의 형태는 다음과 같습니다. 1. 왼쪽부터 채워진 완전 이진 트리이며 2. 자식보다 부모 노드의 값이 큰 최대힙과 자식보다 부모노드의 값이 작은 최소힙이 있다. 탐색을 위한 이진탐색트리(BST)와 다르게, 힙은 최솟값과 최댓값을 찾기 위함입니다. 이때 두 자료구조의 차이점은 BST는 왼쪽 자식 노드 - 부모 ..
