99클럽 코테 스터디 19일차 TIL + 오늘의 학습 키워드 : 힙

백준 1927번 문제 _최소 힙
키워드-힙
문제

자료구조 스택/큐에서 업그레이드 되었다 .!!!


위키백과 -'힙(자료구조)' 설명 아래 첨부
https://naver.me/xIeDAqyR

힙 (자료 구조) - 위키백과, 우리 모두의 백과사전

힙(heap)은 최댓값 및 최솟값을 찾아내는 연산을 빠르게 하기 위해 고안된 완전이진트리(complete binary tree)를 기본으로 한 자료구조(tree-based structure)로서 다음과 같은 힙 속성(property)을 만족한다.

<힙의 종류 2가지>
힙에는 두가지 종류가 있으며, 부모노드의 키값이 자식노드의 키 값보다 항상 큰 힙을 '최대 힙', 부모노드의 키 값이 자식노드의 키 값보다 항상 작은 힙을 '최소 힙'이라고 부른다.
-위키백과 '힙'참고-

최소 힙 설명
힙(Heap)은 완전 이진 트리의 일종으로, 각 노드의 값이 자식 노드의 값보다 작거나 같은 성질을 가진 자료구조입니다. 최소 힙에서는 부모 노드의 값이 자식 노드의 값보다 작거나 같아야 하며, 이를 통해 가장 작은 값을 빠르게 찾고 제거할 수 있습니다. 힙은 주로 우선순위 큐를 구현하는 데 사용됩니다.

문제풀이

이 코드는 파이썬에서  `heapq` 모듈을 임포트하여 최소 힙을 구현합니다.

파이썬 코드
import sys
import heapq

# 입력을 빠르게 받기 위해 sys.stdin.readline 사용
input = sys.stdin.readline

# 최소 힙을 저장할 리스트
min_heap = []

# 연산의 개수 N을 입력받음
N = int(input())

for _ in range(N):
    x = int(input().strip())
    
    if x > 0:
        # x가 자연수일 경우, 힙에 추가
        heapq.heappush(min_heap, x)
    elif x == 0:
        # x가 0일 경우, 힙에서 가장 작은 값을 출력하고 제거
        if min_heap:
            # 힙이 비어있지 않으면 가장 작은 값을 출력
            print(heapq.heappop(min_heap))
        else:
            # 힙이 비어있으면 0 출력
            print(0)

코드 설명
1. 모듈 임포트: `heapq` 모듈을 사용하여 최소 힙을 구현합니다. `sys` 모듈은 입력을 빠르게 받기 위해 사용합니다.
2. 입력 처리: `input` 함수를 사용하여 연산의 개수 `N`을 입력받습니다.
3. 힙 초기화: 빈 리스트 `min_heap`을 생성하여 최소 힙을 저장합니다.
4. 연산 수행:
   - 자연수 `x`가 입력되면 `heapq.heappush`를 사용하여 힙에 추가합니다.
   - `x`가 0일 경우, 힙에서 가장 작은 값을 `heapq.heappop`으로 제거하고 출력합니다. 만약 힙이 비어있다면 0을 출력합니다.

이 코드는 최대 100,000개의 연산을 효율적으로 처리할 수 있으며, 각 연산의 시간 복잡도는 O(log N)입니다.



heapq모듈의 주요 메서드인
heappush와 heappop에 대해 물어보았다.

`heapq` 모듈에서 제공하는 `heappop`과 `heappush` 메서드는 최소 힙(min-heap) 자료구조를 다루기 위한 주요 함수입니다. 이 두 메서드는 힙의 특성을 유지하면서 요소를 추가하거나 제거하는 데 사용됩니다. 아래에서 각각의 특징과 사용법을 설명하겠습니다.

1. `heappush`
특징
- `heappush(heap, item)` 함수는 주어진 `item`을 힙에 추가합니다.
- 힙의 구조를 유지하기 위해 필요한 경우 요소의 위치를 조정합니다.
- 이 함수는 O(log N)의 시간 복잡도를 가집니다.

사용법
```python
import heapq

# 빈 리스트를 힙으로 사용
min_heap = []

# 요소 추가
heapq.heappush(min_heap, 5)
heapq.heappush(min_heap, 3)
heapq.heappush(min_heap, 8)

print(min_heap)  # 출력: [3, 5, 8]
```

위의 예제에서 `heappush`를 사용하여 5, 3, 8을 힙에 추가했습니다. 최소 힙의 특성에 따라 3이 가장 작은 값으로 맨 앞에 위치하게 됩니다.

2. `heappop`
특징
- `heappop(heap)` 함수는 힙에서 가장 작은 값을 제거하고 반환합니다.
- 힙의 구조를 유지하기 위해 필요한 경우 요소의 위치를 조정합니다.
- 이 함수도 O(log N)의 시간 복잡도를 가집니다.
- 힙이 비어있을 경우 `IndexError`가 발생하므로, 사용 전에 힙이 비어있는지 확인하는 것이 좋습니다.

사용법
```python
import heapq

# 힙 초기화
min_heap = [3, 5, 8]
heapq.heapify(min_heap)  # 리스트를 힙으로 변환

# 가장 작은 값 제거 및 반환
smallest = heapq.heappop(min_heap)
print(smallest)  # 출력: 3
print(min_heap)  # 출력: [5, 8]
```

위의 예제에서 `heappop`을 사용하여 힙에서 가장 작은 값인 3을 제거하고 반환했습니다. 그 후 힙은 [5, 8]로 업데이트됩니다.

요약
- `heappush`: 힙에 요소를 추가하는 함수. O(log N) 시간 복잡도.
- `heappop`: 힙에서 가장 작은 요소를 제거하고 반환하는 함수. O(log N) 시간 복잡도.

이 두 메서드를 사용하여 최소 힙을 효율적으로 관리할 수 있습니다.