힙 (Heap) 개념 정리와 면접 질문

Q: 힙의 구조와 특성을 설명해주세요.

완전 이진 트리이면서 부모와 자식 사이에 크기 관계가 있는 구조입니다. | 조건 | 내용 | |------|------| | 모양 | 완전 이진 트리. 위에서 아래로, 왼쪽부터 빈틈없이 채운다 | | 순서 | 부모가 자식보다 작다(최소 힙) 또는 크다(최대 힙) | 형제 사이에는 순서가 없습니다. 그래서 전체 정렬은 아니고 **뿌리가 최솟값(또는 최댓값)이라는 것만** 보장합니다. | 연산 | 복잡도 | |------|--------| | 최솟값 확인 | O(1) | | 삽입 | O(log n) | | 최솟값 제거 | O(log n) | | 임의 값 탐색 | O(n) | 모양이 완전 이진 트리라는 점이 중요합니다. 그래서 포인터 없이 배열로 담을 수 있고 높이가 항상 log n 입니다. **흔한 실수:** 힙을 정렬된 구조로 설명하는 것. 배열로 출력하면 정렬되어 있지 않습니다. 정렬을 얻으려면 하나씩 꺼내야 하고 그것이 힙 정렬입니다.

Q: 힙에서 삽입과 삭제는 어떻게 동작하나요?

완전 이진 트리 모양을 유지한 채로 규칙에 맞는 자리까지 옮깁니다. ``` 삽입 1. 맨 마지막 자리에 넣는다 (모양 유지) 2. 부모와 비교해 더 작으면 자리를 바꾼다 3. 규칙을 만족할 때까지 위로 올린다 삭제 (최솟값 제거) 1. 뿌리를 꺼낸다 2. 마지막 원소를 뿌리로 옮긴다 (모양 유지) 3. 두 자식 중 작은 쪽과 비교해 필요하면 바꾼다 4. 아래로 내려가며 반복한다 ``` 둘 다 높이만큼만 움직이므로 O(log n)입니다. **흔한 실수:** 삭제할 때 두 자식 중 아무 쪽과 비교하는 것. **더 작은 자식**과 바꿔야 새 부모가 두 자식보다 작아집니다. 큰 쪽과 바꾸면 규칙이 다시 깨집니다.

Q: 힙을 배열로 구현하는 방법과 인덱스 공식은?

완전 이진 트리라서 빈틈이 없고, 위에서 아래로 왼쪽부터 번호를 매기면 배열 인덱스가 됩니다. ``` 10(0) / \ 20(1) 15(2) / \ 30(3) 40(4) 배열: [10, 20, 15, 30, 40] ``` | 관계 | 공식 (0부터 시작) | |------|------------------| | 부모 | (i - 1) / 2 의 몫 | | 왼쪽 자식 | 2i + 1 | | 오른쪽 자식 | 2i + 2 | 포인터를 두지 않아 메모리가 적고, 연속 배치라 캐시 효율도 좋습니다. 이 두 이점이 우선순위 큐 구현에서 힙을 표준으로 만든 이유입니다. **흔한 실수:** 완전 이진 트리가 아닌 트리에 이 공식을 쓰는 것. 중간에 빈 자리가 있으면 인덱스가 어긋나 계산이 깨집니다. 그래서 삽입과 삭제에서 모양을 먼저 지키는 것입니다.

Q: 우선순위 큐와 힙의 관계를 설명해주세요.

우선순위 큐는 **무엇을 할지**를 정한 인터페이스이고, 힙은 **어떻게 할지**를 정한 구현입니다. | 구분 | 내용 | |------|------| | 우선순위 큐 | 넣고, 우선순위가 가장 높은 것을 꺼내는 동작을 제공한다 | | 힙 | 그 동작을 O(log n)에 하는 자료구조 | 우선순위 큐를 다른 것으로도 만들 수 있습니다. | 구현 | 삽입 | 최우선 꺼내기 | |------|------|-------------| | 정렬된 배열 | O(n) | O(1) | | 정렬 안 된 배열 | O(1) | O(n) | | 힙 | O(log n) | O(log n) | | 균형 트리 | O(log n) | O(log n). 범위 조회도 된다 | 두 연산이 모두 자주 쓰이므로 한쪽이 O(n)인 구현은 불리하고, 그래서 힙이 기본 선택입니다. **흔한 실수:** 둘을 같은 말로 쓰는 것. 자바의 PriorityQueue 는 이름은 큐지만 내부는 힙이고, 순회 순서는 우선순위 순이 아닙니다.

연산	복잡도
최솟값/최댓값 조회	O(1)
삽입	O(log N)
삭제 (루트)	O(log N)
힙 생성	O(N)

인덱스	0	1	2	3	4
값	1	3	2	7	4

관계	계산
부모	(i - 1) / 2
왼쪽 자식	2i + 1
오른쪽 자식	2i + 2

비교	힙 정렬	퀵 정렬
시간	O(N log N)	O(N log N) 평균
최악	O(N log N)	O(N²)
공간	O(1)	O(log N)
안정성	불안정	불안정
캐시	나쁨	좋음

Q.힙의 구조와 특성을 설명해주세요.

완전 이진 트리이면서 부모와 자식 사이에 크기 관계가 있는 구조입니다.

조건	내용
모양	완전 이진 트리. 위에서 아래로, 왼쪽부터 빈틈없이 채운다
순서	부모가 자식보다 작다(최소 힙) 또는 크다(최대 힙)

형제 사이에는 순서가 없습니다. 그래서 전체 정렬은 아니고 뿌리가 최솟값(또는 최댓값)이라는 것만 보장합니다.

연산	복잡도
최솟값 확인	O(1)
삽입	O(log n)
최솟값 제거	O(log n)
임의 값 탐색	O(n)

모양이 완전 이진 트리라는 점이 중요합니다. 그래서 포인터 없이 배열로 담을 수 있고 높이가 항상 log n 입니다.

흔한 실수: 힙을 정렬된 구조로 설명하는 것. 배열로 출력하면 정렬되어 있지 않습니다. 정렬을 얻으려면 하나씩 꺼내야 하고 그것이 힙 정렬입니다.

Q.힙에서 삽입과 삭제는 어떻게 동작하나요?

완전 이진 트리 모양을 유지한 채로 규칙에 맞는 자리까지 옮깁니다.

삽입
  1. 맨 마지막 자리에 넣는다 (모양 유지)
  2. 부모와 비교해 더 작으면 자리를 바꾼다
  3. 규칙을 만족할 때까지 위로 올린다

삭제 (최솟값 제거)
  1. 뿌리를 꺼낸다
  2. 마지막 원소를 뿌리로 옮긴다 (모양 유지)
  3. 두 자식 중 작은 쪽과 비교해 필요하면 바꾼다
  4. 아래로 내려가며 반복한다

둘 다 높이만큼만 움직이므로 O(log n)입니다.

흔한 실수: 삭제할 때 두 자식 중 아무 쪽과 비교하는 것. 더 작은 자식과 바꿔야 새 부모가 두 자식보다 작아집니다. 큰 쪽과 바꾸면 규칙이 다시 깨집니다.

Q.힙을 배열로 구현하는 방법과 인덱스 공식은?

완전 이진 트리라서 빈틈이 없고, 위에서 아래로 왼쪽부터 번호를 매기면 배열 인덱스가 됩니다.

      10(0)
     /     \
   20(1)   15(2)
   /  \
 30(3) 40(4)

배열: [10, 20, 15, 30, 40]

관계	공식 (0부터 시작)
부모	(i - 1) / 2 의 몫
왼쪽 자식	2i + 1
오른쪽 자식	2i + 2

포인터를 두지 않아 메모리가 적고, 연속 배치라 캐시 효율도 좋습니다. 이 두 이점이 우선순위 큐 구현에서 힙을 표준으로 만든 이유입니다.

흔한 실수: 완전 이진 트리가 아닌 트리에 이 공식을 쓰는 것. 중간에 빈 자리가 있으면 인덱스가 어긋나 계산이 깨집니다. 그래서 삽입과 삭제에서 모양을 먼저 지키는 것입니다.

Q.우선순위 큐와 힙의 관계를 설명해주세요.

우선순위 큐는 무엇을 할지를 정한 인터페이스이고, 힙은 어떻게 할지를 정한 구현입니다.

구분	내용
우선순위 큐	넣고, 우선순위가 가장 높은 것을 꺼내는 동작을 제공한다
힙	그 동작을 O(log n)에 하는 자료구조

우선순위 큐를 다른 것으로도 만들 수 있습니다.

구현	삽입	최우선 꺼내기
정렬된 배열	O(n)	O(1)
정렬 안 된 배열	O(1)	O(n)
힙	O(log n)	O(log n)
균형 트리	O(log n)	O(log n). 범위 조회도 된다

두 연산이 모두 자주 쓰이므로 한쪽이 O(n)인 구현은 불리하고, 그래서 힙이 기본 선택입니다.

흔한 실수: 둘을 같은 말로 쓰는 것. 자바의 PriorityQueue 는 이름은 큐지만 내부는 힙이고, 순회 순서는 우선순위 순이 아닙니다.

힙 (Heap)

힙 (Heap)

종류

시간 복잡도

삽입 과정 (최소 힙)

삭제 과정 (루트 제거)

배열로 구현

우선순위 큐

힙 정렬

Q.힙의 구조와 특성을 설명해주세요.

Q.힙에서 삽입과 삭제는 어떻게 동작하나요?

Q.힙을 배열로 구현하는 방법과 인덱스 공식은?

Q.우선순위 큐와 힙의 관계를 설명해주세요.

더 깊이 공부하기