1. heapq 기본 사용법

파이썬의 heapq 모듈은 기본적으로 최소 힙(min heap)만 지원하며, 최소 힙은 항상 가장 작은 값이 루트(인덱스 0)에 위치한다.

주요 함수:

• heapq.heappush(heap, item): 힙에 원소 추가

• heapq.heappop(heap): 힙에서 가장 작은 원소 제거 및 반환

• heapq.heapify(list): 리스트를 힙 구조로 변환

2. 최대 힙(max heap) 구현 방법

최대 힙: 항상 가장 큰 값이 루트에 위치하는 힙

파이썬에서는 최대 힙을 직접 지원하지 않으므로, 값에 -1을 곱해서 최소 힙에 저장하는 방식으로 구현한다.
따라서, 꺼낼 때도 다시 -1을 곱해 원래 값을 복구해야 한다.

3. 예시 코드

import heapq

# 최대 힙 구현
data = [1, 5, 3, 2, 4]
max_heap = []

# 값에 -1을 곱해서 push
for num in data:
    heapq.heappush(max_heap, -num)

# 가장 큰 값부터 pop
while max_heap:
    print(-heapq.heappop(max_heap))  # 5, 4, 3, 2, 1 순서로 출력

위와 같이 최소 힙의 성질을 이용해 최대값을 빠르게 꺼낼 수 있다.

4. 최대 힙(Max Heap) 자료구조란?

• 완전 이진트리 기반의 자료구조로, 부모 노드가 항상 자식 노드보다 크거나 같은 값을 가진다.

• 루트(맨 위 노드)에 항상 최댓값이 위치한다.

• 삽입/삭제 연산 시에도 힙의 성질(부모 ≥ 자식)을 유지한다.

• 시간복잡도: 삽입, 삭제, 최댓값 조회 모두 O(log n)

• 활용 예시: 우선순위 큐, 실시간 최대값 추출, 작업 스케줄링 등

• 최대 힙은 항상 가장 큰 값을 빠르게 꺼내야 하는 상황에서 매우 유용하다.

5. 요약

1) 파이썬에서 heapq로 최대 힙을 구현하려면 값에 -1을 곱해 최소 힙에 저장하고, 꺼낼 때 다시 -1을 곱해 사용한다.

2) 최대 힙은 부모가 자식보다 크거나 같은 완전 이진트리로, 루트에 항상 최댓값이 위치하는 자료구조이다.

3) heapq를 활용하면 효율적으로 최대값을 빠르게 꺼낼 수 있다.

관련 문제 풀어보기🔗👇https://school.programmers.co.kr/learn/courses/30/lessons/12927#qna