[Algorithm] Binary Heap

Heap 이란? complete binary tree이고, 부모 노드는 항상 자식 노드보다 크거나 같음을 만족하는 자료구조이다.

 

출처: http://code.cloudkaksha.org/binary-tree/types-binary-tree

 

위 사진은 binary tree의 3가지 타입을 보여준다.

full binary tree는 잎 노드를 제외한 노드들의 자식 노드가 0개 혹은 2개인 트리를 말한다.

complete binary tree는 마지막 level을 제외한 모든 level에 노드가 채워져 있고 마지막 level은 최소한 왼쪽으로 노드가 채워진 트리를 말한다.

perfet binary tree는 잎노드를 제외한 모든 노드들의 자식 노드가 2개인 트리를 말한다. 노드의 개수는 2^n-1개 있다.(n은 마지막 level)

 

앞에서 본것처럼 Heap에는 max heap과 min heap이 있다.

이름에서도 알수 있듯이, max heap은 현재 저장하고 있는 값 중 가장 큰 값을 root에 위치시키고,

min heap은 반대로 가장 작은 값을 root에 위치 시킨다.

 

max heap의 삽입 / 삭제 과정을 보자.

 

<<<<<<<<<<<<<<<<<< 삽입 >>>>>>>>>>>>>>>>>>>>>>

삽입 시 제일 마지막 노드에 추가 후 부모 노드보다 추가된 노드의 값이 크면 바꾼다.

<<<<<<<<<<<<<<<<<< 삭제 >>>>>>>>>>>>>>>>>>>>>>

값을 삭제한 후 leaf 노드의 가장 오른쪽 노드의 값으로 채운다. leaf 노드의 가장 오른쪽 노드도 삭제하고
자식 노드와 비교하면서 heap을 재구성한다.

검색에 Heap을 쓴다고 해서 공부해 봄...