1. 최대힙
https://www.acmicpc.net/problem/11279
11279번: 최대 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
최대힙 클래스로 구현
https://velog.io/@gnwjd309/python-heap
[Python] 파이썬 힙(Heap) 사용하기
Heap은 어떻게 구현하나요!
velog.io
# 입력
n = int(input())
numbers = [int(input()) for _ in range(n)]
class MaxHeap:
# 1. 생성하기
def __init__(self):
self.heap = []
self.heap.append(None)
# 2. 삽입하기
# 맨 아래에서 올라가면서 해당 노드가 부모 노드보다 크면 바꾸기 True
def check_swap_up(self, idx):
# 삽입한 모드의 부모 노드가 없을 경우
if idx <= 1:
return False
parent_idx = idx // 2
if self.heap[idx] > self.heap[parent_idx]:
return True
else:
return False
# 데이터 삽입
def insert(self, data):
self.heap.append(data)
idx = len(self.heap) - 1
# check_swap_up()의 값이 참이라면 부모와 위치 바꾸기
while self.check_swap_up(idx):
parent_idx = idx // 2
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
idx = parent_idx
return True
# 3. 삭제하기
# 맨 위에서 내려가면서 해당 노드가 부모 노드보다 크면 바꾸기
# 왼쪽 flag=1, 오른쪽 flag=2
def check_swap_down(self, idx):
left_idx = idx * 2
right_idx = idx * 2 + 1
# 1) 자식 노드가 하나도 없을 경우
if left_idx >= len(self.heap):
return False
# 2) 왼쪽 자식 노드만 있을 경우
# left_idx < len(self.heap)
elif right_idx >= len(self.heap):
if self.heap[left_idx] > self.heap[idx]:
self.flag = 1
return True
else:
return False
# 3) 자식 노드가 모두 있을 경우
else:
if self.heap[left_idx] > self.heap[right_idx]:
if self.heap[left_idx] > self.heap[idx]:
self.flag = 1
return True
else:
return False
else:
if self.heap[right_idx] > self.heap[idx]:
self.flag = 2
return True
else:
return False
# 데이터 삭제
def pop(self):
if len(self.heap) <= 1:
return 0
max = self.heap[1]
self.heap[1] = self.heap[-1]
del self.heap[-1]
idx = 1
# 0 = False, 1 = (왼쪽 자식과 swap), 2 = (오른쪽 자식과 swap)
self.flag = 0
while self.check_swap_down(idx):
left_idx = idx * 2
right_idx = idx * 2 + 1
if self.flag == 1:
self.heap[idx], self.heap[left_idx] = self.heap[left_idx], self.heap[idx]
idx = left_idx
elif self.flag == 2:
self.heap[idx], self.heap[right_idx] = self.heap[right_idx], self.heap[idx]
idx = right_idx
return max
max_heap = MaxHeap()
for number in numbers:
if number == 0:
max = max_heap.pop()
print(max)
else:
max_heap.insert(number)
내장 모듈 heapq를 이용하여 구현
# BOJ_11279 최대힙
import heapq
# 입력
n = int(input())
numbers = [int(input()) for _ in range(n)]
heap = []
for number in numbers:
if number == 0:
if not heap:
print(0)
else:
print(-heapq.heappop(heap))
else:
heapq.heappush(heap, -number)
2. 최소힙
https://www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
최대 최소 힙 heapq 이용하여 구현하기
[Python] heapq를 이용한 최소 힙, 최대 힙
heapq를 이용한 최소 힙과 최대 힙 구현
velog.io
내장 모듈 heapq를 이용하여 구현
# BOJ_1927 최소힙
import heapq
# 입력
n = int(input())
numbers = [int(input()) for _ in range(n)]
heap = []
for number in numbers:
if number == 0:
if not heap:
print(0)
else:
print(heapq.heappop(heap))
else:
heapq.heappush(heap, number)
굳이 클래스로 구현한다면?
# 입력
n = int(input())
numbers = [int(input()) for _ in range(n)]
class MinHeap:
# 1. 생성하기
def __init__(self):
self.heap = []
self.heap.append(None)
# 2. 삽입하기
# 맨 아래에서 올라가면서 해당 노드가 부모 노드보다 작으면 바꾸기 True
def check_swap_up(self, idx):
# 삽입한 모드의 부모 노드가 없을 경우
if idx <= 1:
return False
parent_idx = idx // 2
if self.heap[idx] < self.heap[parent_idx]:
return True
else:
return False
# 데이터 삽입
def insert(self, data):
self.heap.append(data)
idx = len(self.heap) - 1
# check_swap_up()의 값이 참이라면 부모와 위치 바꾸기
while self.check_swap_up(idx):
parent_idx = idx // 2
self.heap[idx], self.heap[parent_idx] = self.heap[parent_idx], self.heap[idx]
idx = parent_idx
return True
# 3. 삭제하기
# 맨 위에서 내려가면서 해당 노드가 부모 노드보다 작으면 바꾸기
# 왼쪽 flag=1, 오른쪽 flag=2
def check_swap_down(self, idx):
left_idx = idx * 2
right_idx = idx * 2 + 1
# 1) 자식 노드가 하나도 없을 경우
if left_idx >= len(self.heap):
return False
# 2) 왼쪽 자식 노드만 있을 경우
# left_idx < len(self.heap)
elif right_idx >= len(self.heap):
if self.heap[left_idx] < self.heap[idx]:
self.flag = 1
return True
else:
return False
# 3) 자식 노드가 모두 있을 경우
else:
if self.heap[left_idx] < self.heap[right_idx]:
if self.heap[left_idx] < self.heap[idx]:
self.flag = 1
return True
else:
return False
else:
if self.heap[right_idx] < self.heap[idx]:
self.flag = 2
return True
else:
return False
# 데이터 삭제
def pop(self):
if len(self.heap) <= 1:
return 0
min = self.heap[1]
self.heap[1] = self.heap[-1]
del self.heap[-1]
idx = 1
# 0 = False, 1 = (왼쪽 자식과 swap), 2 = (오른쪽 자식과 swap)
self.flag = 0
while self.check_swap_down(idx):
left_idx = idx * 2
right_idx = idx * 2 + 1
if self.flag == 1:
self.heap[idx], self.heap[left_idx] = self.heap[left_idx], self.heap[idx]
idx = left_idx
elif self.flag == 2:
self.heap[idx], self.heap[right_idx] = self.heap[right_idx], self.heap[idx]
idx = right_idx
return min
min_heap = MinHeap()
for number in numbers:
if number == 0:
min = min_heap.pop()
print(min)
else:
min_heap.insert(number)