힙(Heap) 시뮬레이션

힙(Heap) 자료구조란?

Heap - 최대값 또는 최소값을 빠르게 구하기 위한 자료구조 - 완전 이진 트리를 기본으로 한 자료구조 - 마지막 레벨을 제외한 모든 레벨에 노드가 꽉 차 있어야 한다. - 트리가 한쪽으로 기울어진

zoosso.tistory.com

배열 인덱스를 통해 쉽게 부모-자식 노드를 알 수 있습니다.

if) 시작 인덱스를 1로 두면 다음과 같이 parent와 child 노드 번호 관계식을 갖습니다.

→ k의 left child 번호 → k × 2

→ k의 right child 번호 → k × 2 + 1

→ k의 parent 번호 → k / 2

시뮬레이션 (최대 Heap 구성)

부모 노드 < 자식 노드인 관계가 존재하므로 원소 위치를 바꾸어야 합니다.

※ Heap을 구성하는 과정을 『Heapify』 라고 합니다.

부모 노드 7 < 자식 노드 15, 14 입니다.

부모노드는 자식 노드 중 더 큰 값인 15와 위치가 바뀝니다.

부모 노드 9 < 자식 노드 12, 10 이므로

부모노드는 자식 노드 중 더 큰 값인 12와 위치가 바뀝니다.

부모 노드 3 < 자식 노드 15, 12 이므로

부모노드는 자식 노드 중 더 큰 값인 15와 위치가 바뀝니다.

(바뀐 위치에서) 부모 노드 3 < 자식 노드 7, 14 이므로

부모노드는 자식 노드 중 더 큰 값인 14와 위치가 바뀝니다.

부모노드 11 > 자식 노드 8, 6 이므로 변화 x

부모 노드 13 > 자식 노드 4, 2 이므로 변화 x

부모 노드 5 < 자식 노드 11, 13 이므로

부모노드는 자식 노드 중 더 큰 값인 13과 위치가 바뀝니다.

(바뀐 위치에서) 부모 노드 5 > 자식 노드 4, 2 이므로 변화 x

최상단 부모 노드 1은 자식 노드보다 작기 때문에

재귀적으로 내려와서 제일 아래(Leaf)에 위치하게 됩니다.

완선된 Heap은 아래와 같습니다.

- Max Heap이므로 Root Node에 위치한 값은 최대값입니다.

- 부모 노드 ≥ 자식 노드 관계 입니다.