이진 힙과 우선순위 큐

이 노트는 우선순위 큐를 배열 기반 이진 힙으로 구현할 때 지켜야 할 불변식과, 갱신·취소·동점·기아까지 확장되는 설계 경계를 다룹니다. 배열 인덱스가 트리 관계를 어떻게 표현하는지부터 확인한 뒤 연산열과 관측 지표로 구현을 검증합니다.

힙의 부분 순서와 전체 정렬의 차이

최소 힙은 각 부모 값이 자식 값보다 크지 않다는 부분 순서를 유지합니다. 루트가 최솟값이라는 것은 알 수 있지만 형제나 서로 다른 부분 트리의 전체 순서는 알 수 없습니다. 배열 [1,4,2,8,5,3]은 최소 힙일 수 있지만 정렬 배열은 아닙니다.

0-based 배열에서 부모는 (i-1)//2, 왼쪽 자식은 2*i+1, 오른쪽은 2*i+2입니다. 실제 구현은 i=0과 배열 끝의 범위를 먼저 확인합니다.

삽입과 추출

push(value):
    append value
    i = last index
    while i > 0 and a[i] < a[parent(i)]:
        swap(a[i], a[parent(i)])
        i = parent(i)

pop_min():
    if empty: return empty-result
    result = a[0]
    move last element to root and shorten array
    sift_down(root):
        choose the smaller valid child
        if parent <= child: stop
        swap and continue from child
    return result

삽입은 아래에서 위로, 추출은 마지막 원소를 루트로 옮긴 뒤 아래로 불변식을 복구합니다. 두 동작은 트리 높이만큼 이동해 O(log n)이며 루트 조회는 O(1)입니다. 배열 자체가 확장되면 한 삽입에 O(n) 재할당이 추가될 수 있어 개별 지연과 상환 비용을 구분합니다. 실무 선택에서는 최솟값만 반복해서 꺼내고 중간 삽입이 많으면 힙을, 전체 순서·범위 검색·중간 원소 조회가 필요하면 정렬 구조나 별도 인덱스를 검토합니다. “O(log n)”은 이동 비용이며 메모리 재할당과 comparator 비용까지 포함한 p99는 별도로 측정해야 합니다.

작은 배열에서의 상향·하향 이동

초기 최소 힙을 [1, 4, 2, 8, 5, 3]으로 두고 0을 넣어 보겠습니다. 배열 끝에 추가한 뒤 부모와만 비교하면서 올라갑니다. 형제끼리는 비교할 필요가 없습니다.

단계	배열	새 값 0의 위치
끝에 추가	[1, 4, 2, 8, 5, 3, 0]	6
부모 2와 교환	[1, 4, 0, 8, 5, 3, 2]	2
부모 1과 교환	[0, 4, 1, 8, 5, 3, 2]	0

새 값이 올라오는 경로 밖의 부모·자식 관계는 변하지 않았습니다. 이 때문에 전체를 다시 정렬하지 않고 한 경로만 복구할 수 있습니다. 아래 그림은 삽입 전 배열이 나타내는 트리입니다. 같은 층의 4와 2 사이에는 정렬 조건이 없다는 점을 보세요.

그림을 글로 읽기

• 인덱스 0 · 값 1
• 인덱스 1 · 값 4: 자식: 인덱스 3의 8 · 자식: 인덱스 4의 5
• 인덱스 2 · 값 2: 자식: 인덱스 5의 3

1. 인덱스 0 · 값 1 → 인덱스 1 · 값 4: 2×0+1
2. 인덱스 0 · 값 1 → 인덱스 2 · 값 2: 2×0+2

이제 삽입 결과에서 최솟값 0을 꺼내면 마지막 값 2를 루트에 옮겨 [2, 4, 1, 8, 5, 3]이 됩니다. 자식 4와 1 중 더 작은 1과 교환하면 [1, 4, 2, 8, 5, 3]으로 복구됩니다. 큰 자식 4와 교환하면 루트 4 아래에 1이 남아 조건이 깨지므로, 내려갈 때 유효한 자식 중 작은 쪽을 고르는 규칙이 중요합니다. 원소가 하나뿐이었다면 제거 후 배열이 비므로 내려갈 루트 자체가 없다는 경계도 처리해야 합니다.

전체 배열의 heapify

이미 n개 값이 있으면 마지막 부모부터 sift-down합니다. 높은 노드는 적고 대부분의 노드는 아래에 있어 적은 거리만 이동합니다. 높이별 노드 수를 합치면 전체 O(n)입니다. 각 값을 순서대로 push하는 O(n log n) 상한의 구성과 다른 방법입니다.

높이 h인 노드는 대략 n/2^(h+1)개 이하이고 각 노드가 내려가는 비용은 O(h)입니다. 전체 비용은 n × Σ(h/2^(h+1)) 형태의 수렴하는 합으로 O(n)이 됩니다. 모든 노드를 최대 높이 log n만큼 움직인다고 세면 실제로 대부분이 잎 근처라는 분포를 놓칩니다.

예를 들어 [5,4,3,2,1]에서 마지막 부모 인덱스 1을 내리면 [5,1,3,2,4], 루트 0을 내리면 [1,2,3,5,4]가 됩니다. 잎은 이미 길이 1의 힙이므로 처리하지 않습니다. 반면 정렬 배열은 최소 조회와 한쪽 끝 제거가 쉬워도 중간 삽입에 이동 O(n)이 필요합니다. 반복 삽입과 최소 추출이 섞이면 힙의 O(log n) 갱신이 유리할 수 있습니다.

우선순위 변경과 취소

힙 안의 작업 우선순위를 10에서 1로 바꿨다고 해 보겠습니다. 숫자만 바꾸면 그 작업은 여전히 배열 아래쪽에 있어, 루트가 최솟값이라는 조건이 깨질 수 있습니다. 바뀐 값을 알맞은 위치로 옮기거나, 옛 항목을 무효로 취급하는 방법이 필요합니다.

• 위치 맵을 사용하는 방법: 작업 ID로 현재 배열 인덱스를 찾고 우선순위를 바꾼 뒤 위나 아래로 이동시킵니다. 두 원소를 교환할 때마다 맵의 인덱스도 함께 고칩니다.
• 지연 삭제하는 방법: 새 우선순위와 버전을 가진 항목을 하나 더 넣습니다. 나중에 옛 버전이 나오면 버립니다. 기존 위치를 찾을 필요는 없지만, 무효 항목이 쌓이면 메모리와 한 번의 pop 지연이 늘어 재구축이 필요합니다.

같은 우선순위의 FIFO가 필요하면 (priority, insertionSequence)를 비교합니다. 순번의 overflow·재시작·ID 재사용을 설계해야 하며, 높은 우선순위가 계속 들어오는 기아는 이 보조 키만으로 해결되지 않습니다.

위치 맵 방식의 삭제는 대상 인덱스 i와 마지막 원소를 교환하고 배열을 줄인 뒤, 새 a[i]가 부모보다 작으면 위로, 그렇지 않으면 아래로 복구합니다. 모든 swap에서 두 원소의 ID→인덱스도 함께 바꿉니다. 마지막 원소 자체를 지웠다면 복구할 i는 없습니다. 같은 ID를 재사용한다면 핸들 세대도 확인해야 새 작업을 옛 취소가 지우지 않습니다.

지연 삭제는 취소를 빠르게 표시하지만 실제 pop 한 번이 무효 항목 수만큼 오래 걸릴 수 있습니다. 유효 작업 수가 줄어도 힙이 계속 크다면 무효 비율·총 메모리 한도를 기준으로 유효 항목만 heapify해 재구축할 수 있습니다. 진단 시에는 pop 결과의 우선순위뿐 아니라 유효 원소의 다중집합, 무효 항목을 건너뛴 횟수, 최대 배열 길이를 함께 기록합니다. 루트만 맞고 내부에 중복 ID나 누락된 작업이 있으면 우선순위 비교 버그가 아니라 삭제·version 관리 버그일 수 있습니다. 재구축 자체는 선형 비용이므로 지연 예산에 반영합니다.

FIFO 보조 순번은 살아 있는 항목끼리 겹치거나 역전되지 않아야 합니다. 고정 폭 순번을 단순 wrap시키면 새 0이 옛 큰 순번보다 앞서 갑니다. 넓은 카운터·비재사용 세대와 순번 조합, 전체 큐가 비었을 때만 초기화하는 정책을 고려합니다. 재시작 후 보관 작업을 복원한다면 다음 순번도 저장된 최대값 이후로 이어야 하며, 단조 시계가 곧 유일한 삽입 순번은 아닙니다.

우선순위 큐의 활용 범위

상위 K명을 유지할 때 크기 K 최소 힙의 루트는 현재 K위 후보입니다. 더 좋은 값이 오면 교체합니다. 하지만 K 밖 값을 버린 상태에서 기존 K위 점수가 내려가면 새 후보를 알 수 없습니다. 동적 순위 전체에는 원본 재스캔이나 정렬 인덱스가 필요합니다.

타이머는 가장 이른 만료를 루트로 관리할 수 있습니다. 만료 항목을 찾는 것과 callback 실행은 별도 단계이며 취소와 실행의 경쟁은 상태 머신으로 보호해야 합니다.

힙 불변식과 연산열 시험

모든 연산 뒤 부모≤자식 조건과 원소 수·다중집합을 검사합니다. push·pop을 섞은 무작위 연산열을 정렬 목록 기준과 비교합니다. 동일 우선순위, 중간 취소, version 재사용, 배열 확장, 무효 항목 폭증을 포함합니다. 예측 결과는 동일 priority에서 insertionSequence가 작은 작업이 먼저 나오고, 취소된 작업은 결과에 나타나지 않으며, 모든 단계에서 부모≤자식이 유지되는 것입니다. 한 번의 실패 뒤에는 마지막 정상 배열과 교환 경로를 남겨 sift-up·sift-down·인덱스 맵 중 어디가 깨졌는지 좁힙니다.