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