[자료구조] 힙(Heap)

힙이란?

데이터에서 최대값과 최솟값을 빠르게 찾기 위해 완전 이진 트리로 구현된 자료구조입니다. 부모 노드가 가진 값이 자식 노드의 값보다 작은 힙을 Min Heap, 부모 노드가 가진 값이 자식 노드보다 큰 힙을 Max Heap 이라고 합니다. 이때 부모노드의 값은 자식 노드보다 무조건 작거나 커야합니다.

위 이미지는 Max Heap의 예시입니다. 루트 노드의 값이 가장 크고 리프 노드를 제외한 자식 노드들 또한 본인의 자식 노드 보다 큰 값을 가지고 있습니다.
이러한 특성을 활용하여 가장 크거나 가장 작은 값을 찾아내기에 적합한 자료구조라고 볼 수 있습니다.

힙의 동작 방식

데이터 삽입

1. 힙은 완전 이진 트리이기 때문에 최하단 노드부터 데이터가 채워집니다.
2. 추가된 노드와 부모 노드의 값을 비교 후 자식 노드가 크다면 서로의 위치를 바꿉니다.
3. 부모 노드가 더 클때까지 2번 작업을 반복합니다.
   

   

시간 복잡도

노드를 추가하는 작업의 최악의 상황은 추가된 노드를 루트 노드까지 비교하는 경우가 최악의 상황일 것 입니다. 이때는 트리의 높이만큼의 비교를 행하게 되고 그에 따라 시간복잡도는 O(logN)입니다.

데이터 삭제

힙에서 데이터가 삭제는 루트(최대 또는 최소)노드를 삭제하는 케이스 밖에 없습니다. 이때 힙의 형태를 갖추도록 하는 과정은

1. 최하위 마지막 자식 노드를 루트로 이동합니다.
2. 자식 노드와 값을 비교 후 자식 노드가 더 크다면 서로의 위치를 변경합니다.
3. 자식 노드의 값이 작을 때 까지 2번 작업을 반복합니다.

시간 복잡도

위 이미지를 보먄 삭제 또한 삽입과 유사한 방식으로 동작하는 것을 확인할 수 있습니다. 삭제의 최악의 상황은 삽입과 마찬가지로 루트부터 최하단까지 값을 비교하는 케이스가 최악의 경우라고 볼 수 있습니다. 따라서 시간 복잡도는 O(logN)이 됩니다.

활용

힙의 특성을 활용하여 우선순위 큐를 구현할 수 있습니다. 일반적인 큐는 FIFO로 먼저 들어온 데이터가 먼저 나간다는 컨셉을 갖고 있지만 우선순위 큐는 들어온 순서와는 관계없이 최대 또는 최소 값을 가진 데이터가 먼저 나가는 컨셉을 갖고 있습니다. 힙을 사용하여 우선순위 큐를 구현한다면 데이터 탐색의 시간 복잡도는 O(1)로 가장 효율적일 것입니다.