힙 자료구조 (heap)
쉽게 풀면
힙은 트리 모양의 자료구조인데, 항상 '부모가 자식보다 크다' 또는 '부모가 자식보다 작다'는 규칙을 지킨다. 이 규칙 덕분에 트리의 맨 위(루트)에는 항상 전체에서 가장 크거나 가장 작은 값이 위치하게 되어, 최댓값이나 최솟값을 즉시 확인하고 꺼낼 수 있다. 우선순위 큐를 구현하는 표준적인 방법이며, 힙 정렬 알고리즘이나 다익스트라 알고리즘의 내부 자료구조로도 쓰인다.
왜 중요한가
힙은 우선순위 큐를 구현하는 가장 표준적인 자료구조이기 때문에 알고리즘, 운영체제, 네트워크 시뮬레이션 등 여러 분야의 논문에서 반복적으로 등장합니다. 최댓값 또는 최솟값을 로그 시간에 꺼낼 수 있다는 성질 덕분에 그래프 최단경로 탐색, 이벤트 기반 시뮬레이션, 작업 스케줄링 등 "다음으로 처리할 원소를 빠르게 골라야 하는" 문제 전반에 활용되며, 새로운 알고리즘을 제안하는 논문에서 시간복잡도를 개선하는 핵심 요소로 자주 언급됩니다.
논문에서는 이렇게 쓰입니다
우선순위가 가장 높은(또는 낮은) 원소를 반복적으로 꺼내야 하는 알고리즘의 자료구조 선택을 설명할 때 쓰인다.
시뮬레이션이나 스케줄링 문제에서 힙이 시간 순서대로 이벤트를 관리하는 자료구조로 쓰이는 사례다.
시스템 소프트웨어 분야에서 힙 기반 우선순위 큐가 자원 할당 순서를 결정하는 데 쓰이는 예시다.
조금 더 깊게 보면
힙은 배열로 구현되는 것이 일반적이며, 특정 인덱스의 부모·자식 관계를 산술 연산만으로 계산할 수 있어 별도의 포인터 없이도 트리 구조를 표현할 수 있습니다. 원소를 넣고 뺄 때마다 힙 속성을 유지하기 위해 원소를 위아래로 이동시키는 연산이 필요하며, 이 과정의 시간복잡도가 트리 높이에 비례해 로그 시간이 되는 원리로 전체 효율성이 보장됩니다. 여러 힙을 병합하는 연산이 잦은 경우에는 이진 힙 대신 피보나치 힙 같은 변형 자료구조가 이론적으로 더 나은 성능을 보인다는 점도 함께 다뤄집니다.
주의할 점
힙은 최댓값이나 최솟값을 빠르게 찾는 데는 강하지만, 임의의 원소를 검색하는 연산은 정렬된 트리와 달리 느리다는 점을 혼동하지 말아야 한다.