힙(Heap)이란?
•
최대값 또는 최솟값을 빠르게 찾아내기 위한 이진 트리이다.
•
이진 검색 트리와 헷갈리지 말 것.
•
최소 힙과 최대 힙에 따라 루트는 최솟값, 최댓값이 될 수 있다.
◦
최소 힙 : 부모는 자식보다 작아야 한다.
◦
최대 힙 : 부모는 자식보다 커야 한다.
•
삽입 : O(log N) 보장
•
삭제 : O(log N) 보장
•
확인 : O(1)
•
PriorityQueue는 기본적으로 최대힙이고, 이를 활용하는 것이 중요하다.
•
힙에서 할 수 있는 것은 균형 이진 트리에서 할 수 있다. 시간 복잡도도 동일하다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현이 쉽고, 공간도 적게 차지한다. 따라서 최소 혹은 최대값의 확인, 삭제만 필요할 때에는 힙을 쓰는 것이 더 좋다.
삽입
•
먼저 원소를 다음 공간에 추가하고, 서로 자리를 바꾸는 방식으로 구현된다.
•
균현 트리임이 보장된다.
•
아래와 같은 상황에서 35보다 더 작은 15를 추가하면, 일단 추가하고 계속 위로 가면서 서로 바꾸면 된다.
•
최악의 경우 최대 높이 만큼 올라가면 된다. 그러나 균형 트리이기 때문에 삽입의 시간 복잡도는 O(log N)이 보장된다.
삭제
•
최솟값을 삭제하면 가장 큰 숫자로 일단 변경한다.
•
그러나 조건이 만족되지 않으면, 루트와 자식 노드를 비교해서 가장 작은 것과 바꾼다.
•
그래도 조건이 만족하지 않으면 위와 같이 반복한다.
•
최대 높이 만큼 내려가면 삭제가 가능하고, 균형 트리이기 때문에 O(log N)을 보장한다.
