힙(Heap)

📌 힙(Heap)이란?

최대값 또는 최솟값을 빠르게 찾아내기 위한 이진 트리이다.
이진 검색 트리와 헷갈리지 말 것.
최소 힙과 최대 힙에 따라 루트는 최솟값, 최댓값이 될 수 있다.
최소 힙 : 부모는 자식보다 작아야 한다.
최대 힙 : 부모는 자식보다 커야 한다.
삽입 : O(log N) 보장
삭제 : O(log N) 보장
확인 : O(1)
PriorityQueue는 기본적으로 최대힙이고, 이를 활용하는 것이 중요하다.
힙에서 할 수 있는 것은 균형 이진 트리에서 할 수 있다. 시간 복잡도도 동일하다. 그러나 힙은 균형 이진 트리보다 수행 속도도 빠르고, 구현이 쉽고, 공간도 적게 차지한다. 따라서 최소 혹은 최대값의 확인, 삭제만 필요할 때에는 힙을 쓰는 것이 더 좋다.

삽입

먼저 원소를 다음 공간에 추가하고, 서로 자리를 바꾸는 방식으로 구현된다.
균현 트리임이 보장된다.
아래와 같은 상황에서 35보다 더 작은 15를 추가하면, 일단 추가하고 계속 위로 가면서 서로 바꾸면 된다.
최악의 경우 최대 높이 만큼 올라가면 된다. 그러나 균형 트리이기 때문에 삽입의 시간 복잡도는 O(log N)이 보장된다.

삭제

최솟값을 삭제하면 가장 큰 숫자로 일단 변경한다.
그러나 조건이 만족되지 않으면, 루트와 자식 노드를 비교해서 가장 작은 것과 바꾼다.
그래도 조건이 만족하지 않으면 위와 같이 반복한다.
최대 높이 만큼 내려가면 삭제가 가능하고, 균형 트리이기 때문에 O(log N)을 보장한다.

📌 참고 자료

TOP