힙 (Binary Heap)

힙(binary heap)이란?

최대값이나 최소값을 빠르게 찾아내기 위해 고안된 완전 이진 트리(마지막 레벨을 제외하고 모두 채워져 있으며, 마지막 레벨은 왼쪽부터 채워져 있는 트리)다. 작은 값을 부모에 놓는 최소힙과 큰 값을 부모에 놓는 최대힙이 있다. 둘은 원리가 같기 때문에 하나만 알아둬도 다른 건 똑같이 사용할 수 있다.

 

최소힙 연산

최소힙은 노드를 추가하거나 삭제할 때마다 부모 노드가 자식노드보다 작은 값을 가지고 있어야 하고, 완전이진트리의 형태를 유지하는 작업(Heapify)이 필요하다.

 

노드 삽입하기

완전 이진 트리의 형태를 유지하기 위해 맨 마지막 레벨의 왼쪽부터 채워나가며, 추가된 노드는 정렬되어있지 않으므로 부모 노드와 비교해 자리를 바꿔가며 정렬시켜줘야 한다. 정렬되어 있는 이진 트리이므로 한 단계를 거칠 때마다 작업이 반으로 줄어들어 O(log n) 의 시간복잡도를 가진다.

 

노드 꺼내오기

최소힙은 최소값을 빠르게 찾아내기 위해 고안되었으니, 노드를 꺼내온다는 건 최소값을 가지는 루트 노드를 요청하는 것이다. 즉, 루트를 꺼내오는 연산이다. 최소힙의 루트를 꺼내면 빈 공간이 생기므로 루트 자리에 맨 마지막 노드(맨 아래 오른쪽)를 올린다. 그 후 자식 노드와 비교해서 자신보다 작은 값을 가진 노드와 바꿔가며 정렬시켜준다. 정렬되어 있는 이진 트리이므로 한 단계를 거칠 때마다 작업이 반으로 줄어들어 O(log n) 의 시간복잡도를 가진다.