HEAP INVARIANT

힙은 전체 정렬이 아니라 루트 후보를 유지하는 구조다

최소 힙은 모든 부모가 자식보다 작거나 같아야 합니다. push와 pop은 이 약속이 깨진 한 경로만 복원합니다.

0-based indexparent=(i-1)//2, left=2i+1, right=2i+2

push새 값을 배열 끝에 넣고 부모보다 우선순위가 높으면 위로 바꿔 올립니다.sift up

top루트 한 칸이 현재 최소값 또는 최대값입니다. 배열 전체가 정렬되어 있을 필요는 없습니다.root

pop루트를 제거하고 마지막 값을 올린 뒤 더 적절한 자식과 바꾸며 아래로 내립니다.sift down

검증: push/pop 뒤 루트가 올바른지와 모든 부모-자식 관계가 불변식을 만족하는지만 확인하면 됩니다.