9장 힙

- 완전 이진 틀리에 있는 노드 중에서 키값이 가장 큰 노드 또는 키값이 가장 작은 노드를 찾기 위해 만든 자료구조다.

- 최대 힙은 [부모노드의 키값 >= 자식노드의 키값]의 관계를 가지는 노드들의 완전 이진 트리다.

- 최소 힙은 [부모노드의 키값 <= 자식노드의 키값]의 관계를 가지는 노드들의 완전 이진 트리다.

- 일반적으로 힙은 최대 힙을 의미한다.

- 같은 키값의 노드가 중복되어 있을 수도 있다.

 

힙 삽입 예시 (17삽입)

힙 삽입 예시 (23삽입)

힙 삭제 예시 (루트 삭제)

완전 이진 트리를 유지해야 하므로 삭제시 마지막 노드를 삭제하고 그 값은 삭제된 자리로 이동한다.