8 Level 0
6 3 Level 1
2 1 Level 2 # -> 이진 트리 O 완전 이진 트리 X 이므로 힙이 아닙니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이4 2 1 Level 2 # 자식 노드보다 크니까 힙이 맞습니다!
8 Level 0
6 3 Level 1 # -> 이진 트리 O 완전 이진 트리 O 인데 모든 부모 노드의 값이4 2 5 Level 2 # 자식 노드보다 크지 않아서 힙이 아닙니다..!
힙은 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리에요
항상 최대/최소의 값들이 필요한 연산이 있다면? 바로 힙을 쓰면 되겠죠!
그러면 힙을 구현하려면 어떻게 해야할까요?
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있도록 하는 자료구조입니다.
다시 말하면 부모 노드의 값이 자식 노드의 값보다 항상 커야 합니다.
그러면 가장 큰 값은 모든 자식보다 커야 하기 때문에 가장 위로 가겠죠!
따라서 최대의 값들을 빠르게 구할 수 있게 되는 것입니다.
#힙의 규칙#
힙은 항상 큰 값이 상위 레벨에 있고 작은 값이 하위 레벨에 있어야 합니다.
따라서, 원소를 추가하거나 삭제할때도 위의 규칙이 지켜져야 합니다!
원소를 추가할 때는 다음과 같이 하시면 됩니다.
- 원소를 맨 마지막에 넣습니다.
- 그리고 부모 노드와 비교합니다. 만약 더 크다면 자리를 바꿉니다.
- 부모 노드보다 작거나 가장 위에 도달하지 않을 때까지 2. 과정을 반복합니다.
예시를 보겠습니다!
이 맥스 힙에서 9를 추가해보겠습니다!
8 Level 0
6 3 Level 1
4 2 1 Level 2
-
맨 마지막에 원소를 넣습니다.
8 Level 0
6 3 Level 1
4 2 1 9 Level 2
2-1. 부모 노드와 비교합니다. 3보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 3 Level 1 4 2 1 9 Level 2
8 Level 0
6 9 Level 1 4 2 1 3 Level 2
2-2. 다시 부모 노드와 비교합니다. 8보다 9가 더 크니까! 둘의 자리를 변경합니다.
8 Level 0
6 9 Level 1 4 2 1 3 Level 2
9 Level 0
6 8 Level 1 4 2 1 3 Level 2
-
가장 위에 도달했으므로 멈춥니다. 힙의 특성을 그대로 유지해 데이터를 삽입했습니다!
9 Level 0
6 8 Level 1
4 2 1 3 Level 2
