#힙

최솟값·최댓값을 빠르게 확인하고 우선순위대로 원소를 처리하는 힙 문제를 다룬다. 현재 4개의 풀이가 있다.

LeetCode 703 Kth Largest Element in a Stream에서 상위 k개만 최소 힙에 유지한다. 새 값이 들어오면 힙 크기를 조절해 k번째 큰 값을 O(log k)에 확인한다.

LeetCode 23 Merge k Sorted Lists에서 각 리스트의 현재 노드만 최소 힙에 둔다. 최솟값을 꺼내고 그 리스트의 다음 노드를 추가해 O(N log k)에 정렬 목록을 병합한다.

프로그래머스 디스크 컨트롤러에서 현재 대기 중인 작업 가운데 소요 시간이 가장 짧은 작업을 최소 힙으로 고른다. 요청 시각과 유휴 시간, 평균 반환 시간을 함께 다룬다.

프로그래머스 이중우선순위큐에서 최소 힙과 음수로 저장한 최대 힙을 함께 사용한다. 값별 개수로 지연 삭제를 처리해 두 힙을 동기화한다.

힙 학습 가이드

필요한 주제만 펼쳐서 힙의 구조와 우선순위 큐를 활용하는 방법을 학습할 수 있다.

힙 기본 개념

힙은 완전 이진 트리 형태를 유지하면서 부모와 자식 사이의 우선순위 규칙을 지키는 자료구조입니다. 최소 힙에서는 부모가 자식보다 작거나 같고, 최대 힙에서는 부모가 자식보다 크거나 같습니다.

힙은 전체 원소를 정렬하지 않고 현재 가장 작은 값이나 큰 값만 반복해서 꺼내야 하는 문제에 적합하다.

힙의 삽입과 삭제

힙에 원소를 추가할 때는 마지막 위치에 넣은 뒤 부모와 비교하며 위로 올립니다. 루트를 제거할 때는 마지막 원소를 루트로 옮긴 뒤 자식과 비교하며 아래로 내립니다.

우선순위 큐 활용 패턴

현재 후보 중 최솟값 또는 최댓값을 반복해서 선택해야 한다면, 후보 전체를 매번 정렬하는 대신 힙에 후보만 유지한다.

Python에서 heapq 사용하기

import heapq

heap = []
heapq.heappush(heap, value)
smallest = heap[0]
smallest = heapq.heappop(heap)

Python의 `heapq`는 최소 힙만 제공하므로 최대 힙이 필요하면 음수를 저장한다. 여러 정보를 함께 저장할 때는 튜플의 앞쪽에 우선순위를 두고, 같은 우선순위를 구분할 고유 순번을 추가한다.

sequence = count()
heapq.heappush(heap, (priority, next(sequence), item))

같은 우선순위의 객체가 서로 비교되지 않는 언어·자료형이라면 이 고유 순번이 비교 오류를 막아 줍니다.

자주 하는 실수