[자료구조] 힙(Heap), 힙 정렬(Heap Sort) 예상 질문

📝 힙 & 힙 정렬 면접 예상 질문

📌 기본 개념

1. 힙이란 무엇인가요?

• 힙이란 완전 이진 트리를 기초로 하는 자료구조로, 부모 노드의 값이 제일 큰 최대힙과 부모 노드의 값이 제일 작은 최소힙으로 나누어집니다.

2. 힙과 이진 탐색 트리(BST)의 차이는 무엇인가요?

• 이진탐색트리는 중위 순회를 하면 왼쪽, 부모, 오른쪽 순으로 정렬된 순서를 보장하지만,
  힙은 부모-자식간의 대소 관계만 보장하며, 좌/우 자식 간 순서는 없습니다.

3. 힙은 왜 배열로 구현할까요?

• 배열은 포인터 관리가 필요없으므로 구현이 단순하고, 힙은 완전 이진 트리 구조라 배열 인덱스만으로도 부모/자식 계산이 가능하므로 배열로 구현합니다.

📌 연산 관련

1. 힙 삽입(insert) 과정과 시간 복잡도는?

• 힙 삽입 과정은 추가할 노드를 가장 말단에 있는 노드의 자식 노드로 추가하고, 그 노드와 부모 노드를 비교해서 규칙에 맞으면 그대로 두고, 아니라면 부모 자리와 교환합니다. 이 순서를 규칙에 맞을때까지 반복하게 됩니다.
  시간복잡도는 O(log n)입니다.

2. 힙 삭제(delete, 보통 루트 삭제) 과정과 시간 복잡도는?

• 힙 삭제 과정은 루트 노드를 제거하고, 마지막 원소를 루트로 이동시킨 후, 루트로 올라간 노드와 그 자식 노드들을 비교합니다. 조건에 만족하면 그대로 두고, 그렇지 않다면 자식과 교환합니다. 조건을 만족할때까지 계속 반복하게 됩니다.
  시간복잡도는 O(log n)입니다.

3. 힙 정렬 과정과 시간 복잡도는?

• 힙 정렬 과정은 크게 두 단계로 나뉩니다.

1. Heapify : 주어진 배열을 최대 힙(혹은 최소 힙)으로 변환합니다.
2. 정렬 반복 : 루트를 배열 끝과 교환하여 힙 크기를 줄이고, 루트에서 Heapify Down를 실행시켜 힙속성을 유지합니다. 이과정을 반복하면 전체 배열이 정렬됩니다.
   시간복잡도는 O(n log n)입니다.

4. 힙 정렬과 다른 정렬 알고리즘(퀵 정렬, 병합 정렬)과의 차이는?

• 시간 복잡도는 비슷하지만, 힙 정렬은 캐시 친화도가 낮아 실제 성능은 퀵 정렬보다 낮을 수 있습니다. 또한 병합 정렬은 안정 정렬인데 비해 힙 정렬은 불안정 정렬입니다.
  [안정 정렬]
  값이 같은 원소의 상대적 순서가 보존됨
  [불안정 정렬]
  값이 같은 원소의 상대적 순서가 보장되지 않음
  [힙정렬이 불안정한 이유]
  동일한 값이라도 배열 뒤쪽 원소가 먼저 앞으로 올 수 있음
  -> 같은 값이라도 heapify 과정에서 자식/부모 교환 순서에 따라 상대적 위치가 바뀔 수 있음
  [병합정렬이 안정한 이유]
  병합과정에서 앞쪽 배열의 원소를 먼저 채택하기 때문에 같은 값일 경우 입력 순서가 유지됨

📌 활용 및 응용

1. 우선순위 큐를 힙으로 구현하는 이유는?

• 삽입/삭제의 복잡도가 O(log n)으로 효율적이며, 정렬된 배열/리스트 기반보다 평균 성능이 우수합니다.

2. 힙은 어떤 상황에서 유용하게 쓰이나요?

• 운영체제의 프로세스 스케줄링
• 다익스트라 알고리즘(최단 경로)
• 작업 스케줄링

3. 힙 정렬이 실무에서 잘 안 쓰이는 이유는?

• 이론적으로는 O(n log n)이지만, 퀵 정렬이 메모리 접근 효율과 캐시 적중률이 더 높아 평균적으로 빨라서 힙정렬은 잘 쓰이지 않습니다.

📌 심화 질문

1. 힙을 최소 힙 / 최대 힙으로 구현할 때 차이는 무엇인가요?

• 최대 힙은 루트에 항상 가장 큰값이 존재하고, 최소 힙은 루트에 항상 작은 값이 존재합니다. 비교 연산 방향만 다를뿐, 삽입,삭제, 일고리즘의 구조는 동일합니다.

2. 힙을 연결 리스트로 구현할 수 있나요?

• 가능하지만, 완전 이진 트리 특성상 배열 구현이 더 효율적이라고 생각합니다.