heapについて
概要
- heapはソートされた状態で要素の追加削除(多くはO(log n))を行うアルゴリズムである
- 多くの場合は二分木を内部的木に構成しており、これによる逐次的なソートの計算を省略することが可能である
ランダウ表記
pythonでの利用例
from heapq import heappush, heappop
h = []
heappush(h, (5, 'write code'))
heappush(h, (7, 'release product'))
heappush(h, (1, 'write spec'))
heappush(h, (3, 'create tests'))
heappop(h) # (1, 'write spec')
heappop(h) # (3, 'create tests')
heappop(h) # (5, 'write code')
heappop(h) # (7, 'release product')
heapqでデータクラスが比較ができない問題に対応する
- heapqの引数に入れるクラスに対して、
__lt__を実装すれば良い
Entity = collections.namedtuple("Entity", ["node", "w"])
Entity.__lt__ = lambda self, other: self.w <= other.w
ヒープソートの例
def heapsort(iterable):
h = []
for value in iterable:
heappush(h, value)
return [heappop(h) for i in range(len(h))]
heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
値が存在しているかのチェック
"any value" in pq
- heapはlog(1)で値のチェックができそうであるが、検索時は
inを使うと線形探索になるのでとても遅い- pythonでは実際に二分木を構築しているわけではないので
log nにはならない - colab
- pythonでは実際に二分木を構築しているわけではないので
例; heapを使うことで順序付きリストを高速に管理する
問題
解答
import heapq
import collections
N = int(input())
S = list(map(int, list(input())))
T = list(map(int, list(input())))
Q = int(input())
que = collections.deque()
pq = []
heapq.heapify(pq)
for i, (s, t) in enumerate(zip(S, T)):
if s != t:
heapq.heappush(pq, i)
for q in range(Q):
flag, s, v = input().split()
s = int(s)-1
v = int(v)
if flag == "S":
S[s] = v
else:
T[s] = v
if S[s] != T[s]:
heapq.heappush(pq, s)
tmp = "="
while pq:
cur = heapq.heappop(pq)
if S[cur] > T[cur]:
tmp = ">"
heapq.heappush(pq, cur)
break
elif S[cur] == T[cur]:
continue
elif S[cur] < T[cur]:
tmp = "<"
heapq.heappush(pq, cur)
break
que.append(tmp)
while que:
print(que.popleft())
例; heapで常に最小値を取り出す
問題
解答
N,K=map(int,input().split())
que = []
for _ in range(N):
a,b = map(int,input().split())
que.append( (a,b) )
import heapq
heapq.heapify(que)
cnt = 0
acc = 0
while que:
a, b = heapq.heappop(que)
cnt += 1
acc += a
heapq.heappush(que, (a + b, b))
if cnt >= K:
break
print(acc)
例; heapqを用いた実装が重い問題
問題
解説
- シミュレーションで解けるがシンプルに実装が重い
解答
import heapq
import collections
N = int(input())
*A, = map(int,input().split())
A1 = A[:N]
A2 = collections.deque(A[N:2*N])
A3 = A[2*N:]
M = [0]*(N+1)
M[0] = sum(A1)
heapq.heapify(A1)
for i in range(N):
s = M[i]
t = heapq.heappop(A1)
s -= t
t2 = max(t,A2.popleft())
s += t2
heapq.heappush(A1,t2)
M[i+1] = s
A2 = collections.deque(A[N:2*N])
A3 = [-a for a in A3]
m = [0]*(N+1)
m[0] = -sum(A3)
heapq.heapify(A3)
for i in range(N):
s = m[i]
t = -heapq.heappop(A3)
s -= t
t2 = min(t,A2.pop())
s += t2
heapq.heappush(A3,-t2)
m[i+1] = s
ans = -float("inf")
for i in range(N+1):
ans = max(ans,M[i]-m[-i-1])
print(ans)