이진 힙(binary heap)과 이를 이용한 힙 정렬(heap sor… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지
1[7급 서울시 알고리즘] 26년 1회차
이진 힙(binary heap)과 이를 이용한 힙 정렬(heap sort)에 대한 설명으로 가장 옳은 것은? (단, 은 힙에 저장된 원소의 개수이다.)1
최소 힙에서 최댓값은 시간에 찾을 수 있다.2
삽입식 힙 생성 알고리즘은 입력 순서와 무관하게 시간이 필요하다.3
힙 정렬은 별도의 배열 없이 제자리(in-place)에서 수행 가능하지만, 안정(stable) 정렬은 아니다.
4
힙 정렬은 시간에 수행 가능하다.해설
힙 정렬은 제자리 정렬이지만 안정 정렬은 아니다.
힙 정렬은 배열 안에서 루트를 마지막 원소와 교환하고 힙을 재구성하므로 추가 배열이 필요 없지만, 멀리 떨어진 원소끼리 교환하기 때문에 같은 키의 상대 순서가 바뀔 수 있다.
- 최소 힙의 최댓값: 리프 어디에나 있을 수 있어 리프 전체(약 절반의 원소)를 살펴야 하므로 이 든다.
- 삽입식 힙 생성: 이미 힙 순서로 들어오는 입력이면 삽입마다 상향 이동이 없어 에 끝나므로 입력 순서와 무관하지 않다.
- 힙 정렬의 시간: 비교 기반 정렬이라 하한을 넘을 수 없으며 이 든다.
오류나 개정된 내용이 보이면 알려주세요