Binary Heap

우선순위가 계속 바뀌는 작업 목록에서 매번 전체를 정렬하면 삽입 비용이 너무 커지고, 단순 array나 linked list로는 가장 작은 값이나 큰 값을 반복해서 찾는 데 많은 스캔이 필요합니다. BST는 순서를 유지할 수 있지만, 최상단 원소 하나만 계속 꺼내는 문제에는 전체 정렬 관계를 유지하는 비용이 과할 수 있습니다. Heap은 이때 필요한 최소한의 질서만 유지해 우선순위 큐 문제를 풀기 위해 쓰입니다.

정렬 알고리즘, 운영체제 스케줄러, 그래프 알고리즘, 시뮬레이션 엔진은 오래전부터 '가장 작은 것 하나를 반복해서 고르는' 연산을 많이 해 왔습니다. 이런 요구는 전체를 항상 정렬된 상태로 유지하는 것보다, 루트 하나만 신뢰할 수 있게 만드는 구조를 요구했습니다. Heap과 heapsort, priority queue가 중요한 이유는 이 선택 연산을 시스템 수준의 공통 도구로 만든 데 있습니다.

Heap은 완전 이진 트리이기 때문에 내부적으로 array 하나로 표현하기 좋습니다. 어떤 인덱스의 자식과 부모 위치를 산술적으로 계산할 수 있어 포인터 없이도 트리 관계를 복원할 수 있습니다. 새 값을 넣으면 마지막 칸에 추가한 뒤 부모와 비교하며 위로 올리는 sift up을 수행하고, 루트를 꺼낸 뒤에는 마지막 원소를 루트로 옮겨 자식과 비교하며 아래로 내리는 sift down으로 heap property를 복구합니다. 이 복구 과정이 heap의 핵심 메커니즘입니다.

Heap과 BST는 둘 다 트리지만 질문이 다릅니다. BST는 '이 값이 어디에 있고, 정렬 순서에서 앞뒤가 무엇인가'를 묻는 구조이고, heap은 '지금 가장 우선인 값이 무엇인가'를 묻는 구조입니다. 그래서 heap은 루트 확인과 추출에는 강하지만 전체를 정렬된 순서로 순회하거나 범위 검색하는 데는 적합하지 않습니다. 또 heap은 array 위에 구현되지만, array처럼 임의 위치의 값을 빠르게 읽기 위한 구조도 아닙니다.

Heap은 작업 스케줄러, 타이머 큐, Dijkstra와 A*의 frontier, Top-K 유지, 여러 정렬된 입력을 병합하는 문제처럼 '가장 먼저 처리할 후보'를 계속 골라야 하는 곳에서 쓰입니다. 예를 들어 알림 발송 시각이 가장 이른 작업을 먼저 꺼내거나, 경로 탐색에서 현재 비용이 가장 작은 정점을 다음으로 확장할 때 heap이 자연스럽습니다. 전체 정렬보다 반복적인 우선순위 선택이 핵심일수록 heap의 장점이 분명해집니다.