힙은 정렬된 배열이 아니다: 우선순위 큐의 배열 순서와 인덱스 공식
heapq나 PriorityQueue를 출력하면 왜 정렬되어 있지 않을까요? 힙이 지키는 조건과 0부터 세는 부모·자식 인덱스 공식, 정렬된 리스트와의 비용 차이, 같은 우선순위 처리를 공식 문서로 정리했습니다.
heapq로 만든 리스트를 출력해 보면 작은 값부터 차례로 놓여 있을 거라는 예상이 빗나갑니다.
import heapq
h = [5, 3, 8, 1, 9, 2]
heapq.heapify(h)
print(h) # [1, 3, 2, 5, 9, 8]
print([heapq.heappop(h) for _ in range(len(h))]) # [1, 2, 3, 5, 8, 9]주석의 출력은 Python 3.14.7에서 실행한 결과입니다. 정확한 내부 배열은 이 버전에서 관찰한 결과일 뿐 API가 보장하지 않습니다. API가 보장하는 것은 힙 조건과 인덱스 0에 최솟값 하나가 있다는 점입니다.
리스트 자체는 정렬되어 있지 않은데, 하나씩 꺼내면 작은 순서대로 나옵니다. 최소 힙은 최솟값 하나가 인덱스 0에 있도록 보장하고, 나머지 배열에는 부모와 자식 사이의 힙 조건만 적용합니다.
힙이 지키는 조건
Python 문서는 최소 힙을, 비교할 원소가 있는 모든 k에서 heap[k] <= heap[2*k+1]과 heap[k] <= heap[2*k+2]가 성립하는 리스트로 정의하고, 원소를 0부터 센다고 적습니다. 배열을 이진 트리로 보면 인덱스 i의 자식은 2*i+1과 2*i+2, 부모는 (i-1)//2입니다.
C++ 공개 표준 초안은 같은 관계를 부모 쪽에서 적습니다. 0 < i < N인 모든 i에 대해 comp(a[⌊(i−1)/2⌋], a[i])가 거짓이면 힙입니다. 1부터 세는 교과서 공식과 다르다는 점은 Python 문서도 따로 언급합니다.
이 조건은 부모와 자식만 비교합니다. 형제끼리나 다른 가지에 있는 노드끼리는 정해진 순서가 없습니다. 위 결과에서 인덱스 1의 3이 인덱스 2의 2보다 커도 문제없는 이유입니다. 둘 다 루트 1의 자식일 뿐입니다. 반대로 정렬된 리스트는 이 조건을 늘 만족하므로, Python 문서 말대로 heap.sort()를 해도 힙 조건이 깨지지 않습니다.
순회 순서는 다른 언어도 약속하지 않는다
Java PriorityQueue 문서는 iterator()와 spliterator()가 원소를 특정 순서로 돌지 않는다고 밝히고, 순서가 필요하면 Arrays.sort(pq.toArray())를 쓰라고 권합니다. toArray()의 결과도 순서가 정해져 있지 않습니다. for-each로 찍은 결과가 뒤죽박죽이어도 버그가 아닙니다.
C++의 std::priority_queue에서 top()은 내부 컨테이너의 front()를 돌려주고, pop()은 pop_heap 다음에 pop_back을 하는 것으로 정의됩니다. 기본 비교자 less를 넣으면 힙 조건은 “부모가 자식보다 작지 않다”가 되어 맨 앞에 가장 큰 값이 옵니다. 최소 힙이 기본인 Python heapq와 반대입니다. Python에도 3.14부터 heapify_max, heappop_max 같은 최대 힙 함수가 생겼습니다.
정렬된 리스트와 무엇이 다른가
정렬된 리스트에 값을 넣을 때 위치는 이진 탐색으로 찾을 수 있습니다. 다만 Python bisect 문서는 O(log n) 탐색 시간이 O(n) 삽입 단계에 묻힌다고 적습니다.
공개된 C++ 표준 초안 기준으로 힙 추가에는 비교 최대 log N번, 맨 앞 제거에는 최대 2 log N번이 필요합니다. Java 문서의 구현 노트도 offer·poll은 O(log n), peek은 상수 시간이라고 적습니다. 반면 Java에서 임의의 원소를 찾는 contains와 remove(Object)는 선형 시간입니다. 이미 있는 리스트를 힙으로 바꾸는 heapify는 제자리에서 선형 시간에 끝납니다.
모든 값을 순서대로 봐야 하면 정렬이 맞고, 값이 계속 들어오는 중에 가장 작은 것만 반복해서 꺼내야 하면 힙이 맞습니다. 가장 작은 값 몇 개만 필요할 때 쓰는 nsmallest도 n이 작을 때 유리합니다. Python 문서는 n이 크면 sorted(), n이 1이면 min()이 더 효율적이라고 안내합니다.
우선순위가 같을 때
힙은 같은 값끼리 들어온 순서를 지키지 않습니다. Java 문서는 최솟값이 여럿이면 그중 어느 원소가 머리에 올지는 임의라고 적습니다. Python 문서는 heapq로 구현한 힙 정렬이 sorted()와 달리 안정적이지 않다고 설명합니다.
넣은 순서를 지키려면 Python 문서가 제안하듯 [우선순위, 삽입 번호, 작업] 형태로 저장해 삽입 번호로 동점을 깨면 됩니다. 번호가 겹치지 않으니 작업 객체끼리 직접 비교할 일도 생기지 않습니다.