006. 힙큐(heapq)를 이용한 문제 풀이와 파이썬에서의 포인터 개념 설명

Leetcode 703. Kth Largest Element in a Stream (Easy)

heapq는 Python의 표준 라이브러리에 포함된 힙 큐(heap queue) 알고리즘을 구현한 모듈입니다. 힙은 특별한 형태의 이진 트리로, 다음과 같은 특징을 가집니다:

1. 최소 힙(min heap): 부모 노드의 값이 항상 자식 노드의 값보다 작거나 같습니다.
2. 완전 이진 트리: 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있고, 마지막 레벨은 왼쪽부터 채워집니다.

heapq 모듈의 주요 특징과 사용법은 다음과 같습니다:

1. 리스트를 사용하여 힙을 구현합니다.
2. 가장 작은 요소가 항상 heap[0]에 위치합니다.
3. 주요 함수들:

• heapq.heappush(heap, item): 힙에 새로운 요소를 추가
• heapq.heappop(heap): 가장 작은 요소를 제거하고 반환
• heapq.heapify(list): 일반 리스트를 힙으로 변환

heapq는 주로 다음과 같은 상황에서 유용하게 사용됩니다:

1. 우선순위 큐 구현
2. 정렬된 상태로 요소를 유지해야 할 때
3. k번째로 큰/작은 요소를 찾을 때

다음은 간단한 사용 예입니다.

import heapq

# 빈 힙 생성
heap = []

# 요소 추가
heapq.heappush(heap, 4)
heapq.heappush(heap, 1)
heapq.heappush(heap, 7)
heapq.heappush(heap, 3)

print("힙 상태:", heap)

# 최소값 추출
smallest = heapq.heappop(heap)
print("추출된 최소값:", smallest)
print("힙 상태:", heap)

# 기존 리스트를 힙으로 변환
numbers = [5, 8, 2, 9, 1, 3]
heapq.heapify(numbers)
print("heapify 후 상태:", numbers)

# 힙에서 모든 요소를 정렬된 순서로 추출
sorted_numbers = []
while numbers:
    sorted_numbers.append(heapq.heappop(numbers))

print("정렬된 숫자:", sorted_numbers)

이 코드를 실행하면 다음과 같은 결과가 출력됩니다:

힙 상태: [1, 3, 7, 4]
추출된 최소값: 1
힙 상태: [3, 4, 7]
heapify 후 상태: [1, 3, 2, 9, 8, 5]
정렬된 숫자: [1, 2, 3, 5, 8, 9]

이 예제에서 볼 수 있듯이:

1. heappush를 사용하여 힙에 요소를 추가합니다.
2. heappop을 사용하여 가장 작은 요소를 제거하고 반환합니다.
3. heapify를 사용하여 일반 리스트를 힙으로 변환합니다.
4. 힙에서 요소를 계속 추출하면 정렬된 순서로 얻을 수 있습니다.

heapq는 최소 힙을 기본으로 구현하지만, 최대 힙이 필요한 경우 요소를 음수로 변환하여 사용할 수 있습니다.