[자료구조/Java] 힙(Heap) 구현

시간이 지나면 자꾸 까먹는다.. 그래서 다시 정리해봐야겠다 자료구조의 핵심 중 하나인 힙(Heap)에 대해 알아보자 힙(Heap) 완전 이진트리의 일종이다. 반정렬 상태(완전히 정렬된 상태가 아님)이며, 완전 이진트리와는 다르게 중복값이 허용된다. 삽입/삭제는 트리 구조이기 때문에 O(logN)이므로 매우 빠르다. 보통 우선순위 큐가 힙으로 많이 구현되는데, 배열과 리스트보다 효율적이기 때문이다. 힙은 최대힙과 최소힙으로 나누어지고, 최대힙은 부모 노드가 가장 큰 것이며 최소힙은 부모 노드가 가장 작은 것이다. 이를 통해 여러 값 중에서 최소 값이나 최대 값을 빨리 찾을 때 유용하게 이용할 수 있다. 힙 자료구조는 보통 배열을 이용하며, 0번째 인덱스는 편하게 구현하기 위해서 사용하지 않는다. 1번째 인..