자료구조 Heap 에 대해 공부해보자!
힙은 완전 이진트리를 기반으로 하는 형태의 자료구조인데 완전이진트리란 마지막을 제외한 모든 노드에서 자식들이 꽉 채워진 이진 트리를 말한다.
힙에는 두가지 종류가 있는데 최대힙(Max Heap) 과 최소힙(Min Heap) 이 존재한다.
최대힙은 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 구조를 유지하고 최소힙은 반대로, 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 구조를 유지한다.
노드 값의 크고 작은 순서가 부모 자식 노드 사이에서만 유지되고 형제 노드사이에선 정렬되지 않기 때문에 힙은 항상 느슨한 반정렬 상태를 유지한다.
힙은 완전 이진트리를 기반으로 하기 때문에 마지막 노드까지 비어있는 공간이 없기에 일반적으로 배열로 구현한다.
최대 힙을 기준으로 했을때 10개의 값 1,2,3,4,5,6,7,8,9,10
삽입된 힙의 형태는 아래와 같이 표현될 것이다.
힙에 데이터를 삽입하거나 루트 노드를 삭제하면 반정렬 상태를 유지했던 힙 구조가 깨질 수 있다. 때문에 힙의 데이터 삽입 삭제과정은 모두 특정 데이터를 삽입 혹은 삭제한 뒤 흐트러진 힙 구조를 재구조화 (Heapify) 하는 과정으로 처리 된다.
데이터를 삽입하거나 삭제하는 과정은 O(1) 시간 안에 이루어지고 흐트러진 힙 구조를 재구조화하는 과정에서 O(logN) 의 시간이 필요하다.
데이터 삽입 삭제 이후 힙을 재구조화 하는 과정은 이미 힙구조가 유지되던 상태에서 간단히 수정하는 과정이었지만 Build Heap 과정은 아예 힙구조가 완성되지 않은 상태의 배열을 힙 구조로 완성 시키는 과정이다.
Build Heap 과정은 재귀적으로 이루어진다.
힙 구조상 가장 아래쪽에 있는, 말단에 가까운 노드들 중 부모 노드들 만을 대상으로 하여 이루어 지는데, 부모노드와 자식 노드 1개 혹은 2개에서 힙구조를 완성하고 다시 부모의 부모 노드로 올라가서 같은 과정을 반복한다.
이러한 Build Heap 과정은 O(NlogN)의 시간 복잡도를 갖는다.