Heap

 

 

Heap은 Complete Binary Tree를 기반으로 한 자료구조!

최댓값이나 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안됐다

 

힙에는 최소힙(Min Heap), 최대힙(Max Heap)이 있다

최소힙은 항상 작은 값이 상위레벨에 위치하도록 하고,

최대힙은 반대로 항상 큰 값이 상위레벨에 위치하도록 한다

 

최소힙에 데이터를 추가하면 마지막 레벨의 왼쪽부터 채워진다

그리고 힙 구조를 유지하기 위해서 자신의 부모노드와 값을 비교하게 된다

만약 부모노드의 값이 더 크다면 자리를 바꾸게 되는데,

이 과정을 부모노드의 값이 더 작을 때 까지 혹은 자신이 루트 노드가 될 때 까지 반복한다

한 번 돌때마다 절반씩 떨어지므로 O(log n)의 시간복잡도를 가진다

 

최소힙에서 최솟값을 찾는건 Root 노드 값을 가져오면 되니까 시간복잡도가 O(1)이 된다

하지만 그 자리를 대체할 다른 노드를 찾아야 하는데,

먼저 제일 마지막 레벨의 제일 끝 노드를 가져와서 루트에 채워준다

이러면 힙 구조가 깨지므로 자신의 자식노드와 비교해가며 heapify 과정을 거쳐야한다

*heapify : 완전 이진 트리를 힙으로 구현하기 위해 재배치시키는 알고리즘
                    왼쪽 자식 노드, 오른쪽 자식 노드 중 더 작은/큰 데이터 값을 가지는 노드를 부모와 바꿈

 

결국 O(log n)의 시간복잡도로 최소값을 찾을 수 있다

 

최대힙의 경우 이와 반대로 생각하면 끝!!