[백준 1927] 최소힙 / Heap

https://www.acmicpc.net/problem/1927

1927번: 최소 힙

 

1. 힙(heap) 이란 ? 

- 우선 순위 큐를 위하여 만들어진 자료구조이다.

- 데이터에서 최댓값과 최솟값을 빠르게 찾기위해 고안된 완전 이진트리

 

자료구조	삭제되는 요소
스택(Stack)	가장 최근에 들어온 데이터
큐(Queue)	가장 먼저 들어온 데이터
우선순위큐(Priority Queue)	가장 우선순위가 높은 데이터

 

 

2. heap을 사용하는 이유? 

- 최솟값이나 최댓값을 찾기 위해 배열을 사용하면 O(n)만큼 시간이 걸린다. 

- 하지만 힙을 사용하면 O(logn)만큼 소요되므로, 배열을 사용할 때보다 빠르게 최솟값과 최댓값을 구할 수 있다.

- 최댓값 또는 최솟값을 빠르게 찾아야 하는 알고리즘 등에 활용된다.

 

 

3. 최대힙 ( Max heap) & 최소힙 (Min heap)

최대힙 (Max heap) & 최소힙 (Min heap)으로 나뉘어진다.

 

- 최소힙: 자식 노드보다 부모 노드의 값이 작다 .                                      - 최대힙 : 자식 노드보다 부모 노드의 값이 크다. 

- 노드가 왼쪽부터 채워지는 완전 이진트리

- 중복 허용

 

4. 힙의 동작 

• 데이터 삽입
  • 힙은 완전 이진 트리이기 때문에, 삽입할 노드는 기본적으로 왼쪽 최하단부 노드부터 채워진다.
  • 채워진 노드의 위치에서, 부모 노드의 값보다 클 경우에는 부모노드와 위치를 바꾸며 이를 반복한다.
• 데이터삭제
  • 데이터가 삭제된다면 가장 큰 값인 부모 노드의 값이 삭제된다.

 

내 코드 

arr_list = [] # 배열 초기화 
N = int(input()) #연산의 개수 
for i in range(N): 
    n = int(sys.stdin.readline()) 
    if n > 0: 
        arr_list.append(n) 
        arr_list.sort() #오름차순 정렬 
    elif n==0: 
        if len(arr_list)==0: 
            print(0) 
        else:
            print(arr_list[0]) 
            arr_list.remove(arr_list[0])

 

코드 

import heapq
import sys

arr_heap = []  # 최소 힙 초기화
N = int(input())  # 연산의 개수

for _ in range(N):
    n = int(sys.stdin.readline())
    
    if n > 0:
        heapq.heappush(arr_heap, n)  # 양수일 경우 최소 힙에 원소 추가
    elif n == 0:
        if not arr_heap:
            print(0)
        else:
            print(heapq.heappop(arr_heap))  # 최소 힙에서 원소를 뽑아서 출력

 

 

import heapq는 생소한데.. 

파이썬에서 제공하는 우선순위큐인  heapq 모듈로 하면 시간초과가 안난다. 

heapq는 따로 리스트를 만들고 이 리스트를 heapq메소드의 인자로 사용해야 한다. 

 

 

1. 삽입  - 힙에 원소를 추가한다. 

heapq.heappush(list, value) 

 

 

2. 삭제 - 힙에 원소를 삭제한다. 

heapq.heappop(list) 

 

import heapq

# 리스트를 힙으로 변환
lst = [4, 1, 7, 3, 8, 5]
heapq.heapify(lst)
print(lst)  # 출력: [1, 3, 5, 4, 8, 7]

# 힙에 원소 추가
heapq.heappush(lst, 2)
print(lst)  # 출력: [1, 2, 5, 3, 8, 7, 4]

# 가장 작은 원소 제거
min_element = heapq.heappop(lst)
print(min_element)  # 출력: 1
print(lst)  # 출력: [2, 3, 5, 4, 8, 7]

# 힙에 원소 추가하고 가장 작은 원소 제거
min_replaced = heapq.heappushpop(lst, 6)
print(min_replaced)  # 출력: 2
print(lst)  # 출력: [3, 4, 5, 6, 8, 7]

# 가장 작은 원소 제거하고 새로운 원소 추가
min_replaced = heapq.heapreplace(lst, 9)
print(min_replaced)  # 출력: 3
print(lst)  # 출력: [4, 6, 5, 9, 8, 7]

 

 

3. 최소 값 얻기 

list[0] 

- heapq 모듈을 사용하여 리스트에 값을 넣을 때 항상 가장 작은 값이 인덱스 0에 존재. 

- 오름차순으로 정렬하는게 아님 

 

- " 기본적으로 heapq는 최소 힙이기 때문에 만약 최대 힙으로 바꾸고 싶다면 단순히 값을 넣을 때 음수로 바꾸어서 넣고 값을 뺄때 양수로 바꾸어서 빼내면된다. " 

----> 부가설명 

 

heapq 모듈은 기본적으로 최소 힙을 지원합니다. 그래서 만약 최대 힙을 원한다면 간단한 트릭을 사용할 수 있습니다.

여러분이 힙에 값을 추가할 때, 그 값을 음수로 바꾸어 넣으면 됩니다. 그러면 가장 작은 값이 사실상 가장 큰 값이 되겠죠. 그리고 값을 꺼낼 때는 다시 양수로 돌려놓으면 됩니다.

간단한 예시로 설명하면:

import heapq

# 최대 힙으로 사용할 리스트
max_heap = []

# 최대 힙에 값을 추가할 때는 음수로 변환하여 추가
heapq.heappush(max_heap, -4)
heapq.heappush(max_heap, -1)
heapq.heappush(max_heap, -7)

# 최대 힙에서 값을 꺼낼 때는 다시 양수로 변환하여 꺼냄
max_value = -heapq.heappop(max_heap)

print(max_value)  # 출력: 7

이런식으로 음수를 활용하면 최대 힙을 구현할 수 있습니다. 이는 힙 자료구조의 특성을 이용하여 값을 반전시키는 아이디어입니다.