힙(Heap) 자료구조는 어떤 성질을 이용해 우선순위 큐(Priority Queue)를 효율적으로 구현하나요?

이렇게 답해 보세요 (핵심 답변)

이진 힙은 왼쪽부터 빈틈없이 채워지는 '완전 이진 트리' 모양과, 부모가 자식보다 항상 우선순위가 높거나 같다는 '힙 순서 성질'을 함께 유지하는 자료구조입니다. 최소 힙 기준으로 루트에 항상 최솟값이 있어 최솟값 조회는 O(1)이고, 끝에 넣어 위로 올리는 삽입과 루트를 빼고 마지막 원소를 옮겨 아래로 내리는 삭제는 트리 높이인 O(log n)에 수행됩니다. 전체가 정렬된 구조는 아니므로 임의 값 검색은 일반적으로 O(n)이 걸립니다.

함께 설명하면 좋은 이유 (꼬리질문 대비)

1. 완전 이진 트리 형태 덕분에 별도 포인터 객체 없이 일반 배열의 인덱스 계산만으로 부모와 자식 위치를 효율적으로 찾아갈 수 있습니다.
2. 자료구조에서 말하는 힙(Heap)은 런타임 동적 메모리 할당 영역을 부르는 메모리 힙(Heap)과 이름만 같을 뿐 다른 개념입니다.

면접에서 자주 하는 실수

부모와 자식 사이의 대소 관계만 유지될 뿐인데 형제 노드나 배열 전체까지 크기순으로 정렬되어 있다고 추론하면 안 됩니다.