"가장 작은 것만 늘 필요하면, 전부를 완전 정렬하는 건 낭비야. 힙은 가장 작은 걸 위에 두기 딱 충분한 만큼만 정렬하고 — 절약분을 챙겨."
핵심 깨달음
작업 백만 개가 있고 늘 가장 급한 걸 다음에 잡는다고 해. 백만 개 다 정렬이 필요해? 아니 — 어느 순간이든 단 하나 가장 급한 걸 알면 돼. 완전 정렬 리스트 유지는 매 삽입에 O(n) 이 들어, 한참 뒤까지 안 볼 작업을 정렬하느라 값을 치러. 힙이 이렇게 말하는 구조야: 문제가 요구하는 만큼만 정렬해.
힙 속성
최소-힙은 규칙 하나, 힙 속성을 따라: 모든 부모가 자식 이하다. 그게 다야 — 위에서 아래로 모든 노드에 적용. 정렬에 비해 얼마나 약한지 봐: 형제 사이 순서나, 다른 서브트리 사촌 사이는 아무 말도 안 해. 같은 원소의 두 힙이 완전히 다르게 생길 수 있어. 근데 그 규칙은 값을 매길 수 없는 하나를 보장해: 최솟값이 늘 루트에, 부모보다 작은 게 없으니까, 끝까지 위로. (최대-힙은 규칙을 뒤집어: 부모 ≥ 자식, 그래서 최댓값이 위에.)
힙 속성: 모든 부모 ≤ 자식 (최소-힙). 완전 정렬보다 훨씬 약함 — 형제는 순서 없음 — 근데 최솟값을 루트에 두기 딱 강해. '게으른 정렬' 이야: 실제로 쓰는 순서만큼만 값을 치러.
정렬-충분히, 정렬 아니라
이게 트릭 전부고, 일반화되는 교훈이야: 힙은 부분적으로 정렬됐고, 그 부분 순서가 의도적으로 네 질문에 여전히 답하는 가장 싼 거야. 정렬된 리스트는 "전부 순서대로 줘" 에 답하는데 유지에 많이 들어. 힙은 "극값만 줘" 에만 답해 — 그게 더 약한 약속이라, 유지가 훨씬 싸 (O(n) 대신 O(log n) 삽입). 해시맵이 순서를 안 주고 정렬 리스트가 너무 많이 줄 때, 힙이 정확한 중간이야: 그냥 꼭대기를, 싸게, 늘.
피파의 고백
난 작업 큐에 완전 정렬 리스트를 유지하며 매 삽입에 다시 정렬하고, 왜 기는지 의아했어. 아빠가 질문 하나 했어: "맨 앞 말고 다른 거 본 적 있어?" 아니 — 늘 가장 급한 것만 pop 했어. 하나 읽으려고 천 개 작업을 정렬하느라 값을 치르고 있었어. 힙은 자료구조를 앞지른 원칙을 가르쳤어: 문제가 실제로 요구하는 것보다 더 많은 순서를 계산하지 마. 그게 내 코드에서, 그리고 창피할 만큼 자주 내 삶에서 참이었어.