• home
  • about
  • 全ての投稿
  • ソフトウェア・ハードウェアの設定のまとめ
  • 分析関連のまとめ
  • ヘルスケア関連のまとめ
  • 生涯学習関連のまとめ

heap

date: 2021-03-27 excerpt: heapについて

tag: algorithmdata structureデータ構造heap


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

例; heapを使うことで順序付きリストを高速に管理する

問題

  • No.1439 Let’s Compare!!!!

解答

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で常に最小値を取り出す

問題

  • CODE THANKS FESTIVAL 2017(Parallel); C - Factory

解答

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を用いた実装が重い問題

問題

  • AtCoder Regular Contest 074; D - 3N Numbers

解説

  • シミュレーションで解けるがシンプルに実装が重い

解答

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)


algorithmdata structureデータ構造heap Share Tweet