힙(Heap)개념 (2)

최소 힙에서 데이터 삽입 과정은 다음과 같다.

1. 완전 이진 트리 순서로 새 데이터를 넣는다.

2. 만약 부모노드가 존재한다면, 부모 노드보다 자식 노드의 우선순위가 낮다면 부모노드와 자식노드의 위치를 바꾼다.

3. 계속해서 루트노드까지 반복한다.

최대 힙에서 데이터 삽입 과정은 다음과 같다.

1. 완전 이진 트리 순서로 새 데이터를 넣는다.

2. 만약 부모노드가 존재한다면, 부모 노드보다 자식 노드의 우선순위가 높다면 부모노드와 자식노드의 위치를 바꾼다.

3. 계속해서 루트노드까지 반복한다.

최대 힙에서 삭제 과정은 다음과 같다.

이 그림을 통해 보자면

1. 트리의 루트 노드를 삭제한다.

2. 그리고 완전 이진 트리에서 가장 마지막에 위치한 노드를 루트 노드로 옮긴다.

3. 루트 노드로 올라간 노드는 순차적으로 삽입과정과 동일하게 비교를 하여 자신의 위치로 찾아간다.

** 주의 **

최소 힙에서는 루트 노드로 올라간 노드를 자식 노드와 비교 할 때는 자식 노드중 작은 값과 교환하여야 한다.

만약 어떤 루트 노드가 삭제되고 16이 가장 위로 올라 왔을 때, 15와 교환되면

15는 다시 14와 교환되어야 하는 상황이 일어나기에,

최소 힙에서는 자식 노드 중 작은 값과 교환 되어야 한다.

(최대 힙은 한번 생각해 보길 바란다.)