✒️ 0. 들어가기 전
힙과 우선순위 큐는 데이터의 우선순위를 관리하는 데 필수적인 자료구조로, 주로 최댓값이나 최솟값을 빠르게 찾기 위해 사용된다.
아래에서 힙의 구조, 힙 정렬, 그리고 우선순위 큐의 구현 방법을 배워보자.
✒️ 1. 힙(Heap)
힙은 완전 이진 트리(Complete Binary Tree) 구조로, 노드 간의 특정 관계를 유지하여 데이터 중 가장 크거나 작은 값을 빠르게 찾아내는 자료구조이다. 힙은 크게 최대 힙과 최소 힙으로 나뉜다.
💡 최대힙과 최소힙
최대 힙(Max Heap): 부모 노드의 값이 자식 노드의 값보다 항상 크거나 같은 구조를 가진다.
최댓값은 항상 루트 노드에 위치하므로, O(1) 시간 복잡도로 최댓값을 찾을 수 있다.
최소 힙(Min Heap): 부모 노드의 값이 자식 노드의 값보다 항상 작거나 같은 구조를 가진다.
최솟값은 항상 루트 노드에 위치하므로, O(1) 시간 복잡도로 최솟값을 찾을 수 있다.
💡 힙의 데이터 삽입
힙에 데이터를 삽입할 때는 다음과 같은 절차를 따른다.
1. 리프 노드(가장 마지막 노드) 위치에 새로운 데이터를 삽입.
2. 삽입된 노드와 그 부모 노드를 비교.
3. 힙의 성질을 유지하기 위해 필요한 경우 부모 노드와 자식 노드의 위치를 교환.
4. 루트 노드에 도달하거나, 힙의 성질이 만족될 때까지 이 과정을 반복.
💡 힙의 데이터 삭제
힙에서 데이터를 삭제할 때는 루트 노드만 삭제할 수 있다.
1. 루트 노드를 제거.
2. 가장 마지막 노드를 루트 노드 위치로 이동시킴.
3. 이동된 노드와 그 자식 노드들을 비교.
4. 힙의 성질이 만족될 때까지 자식 노드와 위치를 교환.
💡 힙과 이진 탐색 트리의 차이점
힙과 이진 탐색 트리는 모두 이진 트리 구조를 가지지만, 그 목적과 구조에서 차이가 있다.
이진 탐색 트리는 노드가 왼쪽 자식 노드보다 크고, 오른쪽 자식 노드보다 작은 값으로 정렬된다.
반면, 힙은 부모 노드가 자식 노드보다 크거나 작은 힙 특성만을 유지한다.
이진 탐색 트리는 데이터 탐색에 최적화되어 있으며, 중위 순회(in-order traversal)시 데이터가 정렬된 순서로 출력된다.
힙은 최댓값이나 최솟값을 빠르게 찾는 데 최적화되어 있다.
💡 시간복잡도
- 참조(최대 또는 최소값을 참조) : O(1)
- 탐색 : O(n)
- 삽입 / 삭제 : O(logn)
📝 면접 예상 질문
Q. 힙과 이진 탐색 트리의 차이점은 무엇인가요?
A. 힙은 완전 이진 트리로, 최대/최소값을 빠르게 찾기 위해 사용되며, 자식 노드 간의 대소 관계가 없고, 부모 노드와의 관계만 중요합니다. 반면 이진 탐색 트리는 탐색을 위해 만들어진 트리로, 왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 큽니다.
