How it works?

이진 힙(binary heap)은 일반 배열 내에 존재합니다. 인덱스 i(0부터 시작)에 있는 노드의 경우, 그 자식 노드들은 2*i + 1과 2*i + 2에 위치합니다. 이러한 인덱싱 방식이 트리를 배열 안에 담을 수 있게 하는 핵심 기법입니다.

단계별 프로세스:

1. 최대 힙(max-heap) 구성: 모든 부모 노드가 자식 노드보다 크거나 같도록(>=) 배열을 재배치합니다. 가장 큰 값이 인덱스 0에 위치하게 됩니다.
2. 최댓값 추출: 루트(가장 큰 값)를 힙의 마지막 요소와 교체한 다음, 힙의 크기를 하나 줄여서 가장 큰 값이 배열의 끝에 최종 정렬된 상태로 고정되게 합니다.
3. sift-down으로 복구: 새로운 루트 노드가 제자리에 있지 않을 수 있으므로, 힙 속성이 다시 유지될 때까지 sift-down(더 큰 자식 노드와 교체하는 과정을 반복)을 수행합니다.
4. 반복: 힙이 빌 때까지 이 과정을 반복합니다. 이제 배열은 오름차순으로 정렬됩니다.

[4, 10, 3, 5, 1] 예시:

• 최대 힙 구성: [10, 5, 3, 4, 1].
• 루트인 10을 끝으로 보내고 sift-down을 수행한 뒤, 5, 4, 3에 대해 이 과정을 반복합니다.
• 결과: [1, 3, 4, 5, 10].