Heap audit

힙은 정렬이 아니라 부모-자식 조건 복원

힙 배열은 전체 순서를 보장하지 않습니다. push는 위로, pop과 heapify는 아래로 내려가며 깨진 한 경로만 다시 맞춥니다.

최소 힙 배열 예시

3i0 5i1 8i2 9i3 7i4 12i5 10i6

검사는 parent(i) 값이 child(i) 값 이하인지에 집중합니다.

push

끝 삽입 뒤 위로

새 값이 부모보다 작으면 교환하며 루트 방향으로 이동합니다.

비용 O(log N)
pop

루트 제거 뒤 아래로

마지막 값을 루트에 놓고 더 작은 자식과 비교해 내려갑니다.

비용 O(log N)
heapify

마지막 부모부터

각 서브트리를 아래로 복원하므로 전체 구축은 O(N)입니다.

배치 입력에 적합
top

루트만 확인

현재 극값 조회는 빠르지만 정렬된 전체 출력은 아닙니다.

비용 O(1)