최대 힙 (Heap) 이란? 최대 힙 (Max Heap) 은 아래 그림과 같이, 부모의 값이 자식의 값보다 항상 큰 자료구조이다. 항상 루트에 최대 값을 가지기 때문에, 이를 이용해서 우선순위 큐 (Priority Queue) 를 구현할 수 있다. 최대 힙의 시간 복잡도는 삽입 (Push) 할 때 O (log N), 삭제 (Pop) 할 때 O (log N) 이므로, 굉장히 합리적인 자료구조임을 알 수 있다. * 참고로 위의 그림에서 루트가 최소가 되는 구조라면 최소 힙 (Min Heap) 이 된다. 동작 원리 최대 힙은 배열을 통해서 구현한다. 위의 최대 힙을 배열로 나타내면 다음과 같다. 이 그림에서 알 수 있듯이, 배열을 통해서 구현하면 다음의 사실을 이용할 수 있다. - 부모의 인덱스 * 2 = 왼..