힙 push/pop 불변식

힙 불변식

힙에서 중요한 것은 트리가 정렬되어 있다는 착각을 버리는 것입니다. 힙은 루트가 최댓값 또는 최솟값이라는 조건과 완전 이진트리 모양만 보장하며, push와 pop은 위로 올리기와 아래로 내리기로 이 두 조건을 복구합니다.

01

배열 인덱스 연결

0-based 배열에서는 parent=(i-1)/2, left=2i+1, right=2i+2 관계를 사용합니다.

index
02

push 후 위로 올린다

마지막 위치에 삽입해 모양을 지키고, 부모와 비교하며 order 조건을 복구합니다.

sift up
03

pop 후 아래로 내린다

루트를 제거하고 마지막 원소를 루트로 옮긴 뒤 더 우선순위 높은 자식과 바꿉니다.

sift down
04

동률 정책 결정

힙 자체는 안정 정렬을 보장하지 않으므로 같은 우선순위의 출력 순서를 별도로 관리합니다.

tie
Root only
전체 정렬이 아니라 루트 우선순위만 보장 배열을 그대로 출력해도 정렬 결과가 되지는 않습니다.
not sorted
push/pop
각각 O(log N) 높이만큼 이동 완전 이진트리 높이가 log N이기 때문입니다.
cost
heapify
전체 배열을 O(N)에 힙으로 만들 수 있음 모든 원소를 push하는 O(N log N)과 구분합니다.
build

인덱스 경계 · 정렬 착각 · 동률 점검

인덱스 경계 자식이 하나만 있는 마지막 내부 노드를 따로 확인합니다.
정렬 착각 힙 배열의 형제나 사촌 사이에는 정렬 관계가 없습니다.
동률 동일 priority 안정성이 필요하면 삽입 순번을 함께 저장합니다.