2025 국가직9급 컴퓨터일반 18번 해설 — 힙

① 삽입 시간 복잡도는 이다

이 선지 진술은 틀림(X)

이진 힙 삽입은 끝에 원소를 넣은 뒤 위로 올리는 heapify-up 과정이 필요하므로 일반적으로 O(log n)이다.

② 힙은 우선순위 큐의 한 종류이다

이 선지 진술은 옳음(O)

힙은 최댓값이나 최솟값을 빠르게 찾고 삭제할 수 있어 우선순위 큐 구현에 자주 사용된다.

③ 힙은 완전 이진 트리를 사용한다

이 선지 진술은 옳음(O)

힙은 완전 이진 트리의 구조적 성질과 부모-자식 간 우선순위 성질을 함께 만족하는 자료구조이다.

④ 최대 힙(Max Heap)은 부모노드의 키값이 자식노드의 키값보다 크거나 같다

이 선지 진술은 옳음(O)

최대 힙은 루트에 가장 큰 키가 오도록 부모 키가 자식 키 이상이라는 힙 순서 속성을 만족한다.