배열 전체를 힙으로 만들 때 bottom-up heapify는 왜 반복 삽입보다 낮은 전체 비용을 가질 수 있나요?
꼬리 질문을 독립 문항으로 확장했습니다. 원래 문항에서 맥락 보기 →
잠깐, 답변을 보기 전에
먼저 내 말로 설명해 볼까요?
답변과 점검 포인트 펼치기답변 접기
01
구두 답변
정의를 외우기보다, 원리와 조건을 연결해 설명해 보세요.
아래쪽 부모부터 sift-down하면 대부분의 노드는 낮은 높이만 내려갑니다. 높이 h인 노드 수가 대략 n/2^(h+1)이므로 이동량을 합하면 O(n)으로 제한됩니다.
반복 삽입의 O(n log n) 상한과 구분하고 빈·동일값·정렬 입력을 시험합니다. heapify는 전체 정렬이 아니라 부모·자식 부분 순서만 만듭니다.
02
득점 포인트
이해가 드러나는 지점을 확인해 보세요.
- 아래쪽 부모부터 sift-down하면 대부분의 노드는 낮은 높이만 내려갑니다. 높이 h인 노드 수가 대략 n/2^(h+1)이므로 이동량을 합하면 O(n)으로 제한됩니다.
- heapify는 전체 정렬이 아니라 부모·자식 부분 순서만 만듭니다.
03
감점 포인트
놓치기 쉬운 조건과 오해를 짚어 보세요.
- 다음 핵심 구분을 반대로 설명하거나 성립 조건을 생략한다: 아래쪽 부모부터 sift-down하면 대부분의 노드는 낮은 높이만 내려갑니다.
04
더 파고들 거리
하나 더 질문하며 이해의 범위를 넓혀 보세요.
득점·감점 포인트는 학습용 자기 점검 기준이며, 특정 회사의 실제 채점표가 아닙니다.
원리부터 공부하고 싶다면
답변을 보충하는 개념·예제·슈도코드를 읽어 보세요.