우선순위 기반 데이터 처리를 위한 힙(Heap)과 우선순위 큐를 정리한다.
힙(Heap) 구조 분석
힙은 부모-자식 노드 간 대소 관계를 유지하는 완전 이진 트리이다.
[ 최대 힙(Max Heap) 구조 ]
[ 90 ] (루트: 최댓값)
/ \
[ 80 ] [ 70 ]
/ \ /
[ 50 ][ 60 ][ 40 ]
-
최대 힙: 부모 노드가 자식 노드보다 크거나 같다.
루트에 최댓값이 위치한다. -
최소 힙: 부모 노드가 자식 노드보다 작거나 같다.
루트에 최솟값이 위치한다.
데이터 삽입 및 삭제 시 힙 구조 유지 복잡도는 O(log N)이다.
우선순위 큐(Priority Queue)
데이터 입력 순서와 무관하게 우선순위가 높은 데이터를 먼저 배출한다.
힙을 통해 효율적으로 구현 가능하다.
- 삽입: 종단 노드 추가 후 부모와 비교하며 위치를 조정한다.
- 삭제: 루트 노드 추출 후 종단 노드를 루트로 이동시켜 재정렬을 수행한다.
힙은 프로세스 스케줄링 등 우선순위 제어가 필요한 시스템에서 성능적 이점을 제공하는 것 같다.
