최소 힙 - 제일 급한 것부터 꺼내는 구조

힙(heap) = "부모가 항상 자식보다 작다(최소 힙)" 규칙을 지키는 트리 구조. 배열로 표현합니다: i번째 부모의 자식은 2i+1, 2i+2 번째.

        (1)          ← 루트 = 항상 최솟값
       /   \
     (3)   (2)
     / \
   (7) (5)

• peek: 최솟값 보기 → 그냥 루트 보면 됨 → O(1)
• push: 끝에 추가 후 부모와 비교하며 올림 (_heapify_up) → O(log n)
• pop: 루트 꺼냄, 마지막 원소를 루트로 옮긴 뒤 자식과 비교하며 내림 (_heapify_down) → O(log n)

왜 TTL 관리에 힙이 적합한가?

TTL = (expire_at, key)를 저장하고, 가장 먼저 만료되는 것을 계속 물어봐야 합니다.

• 만료 시각이 가장 작은 것 = 최솟값 → 힙의 루트에 항상 있음!
• 매번 전체를 정렬하거나 순회하는 것보다 훨씬 효율적입니다.

---

출처: Codyssey-B1/B5-1