Day 138-Q1 | 基数ヒープ（Radix Heap）

問題

非負整数をキーとする優先度付きキューに対して、$Q$ 個のクエリを順番に処理せよ。

0 x : キューに整数 $x$ を1つ追加する。
1 : キューの最小値を出力し、その要素をキューから取り除く。キューが空なら -1 を出力する。

本問はダイクストラ法のキューとして使う場面を想定しており、次の単調性の制約が保証される：クエリ 0 x が実行される時点までに少なくとも1回 1 が実行されていた場合、その $x$ は直前に出力された値以上である。

この制約を利用し、値を「直前の最小値とのXORの最上位ビット位置」で分類するバケツ（基数ヒープ）を用いることで、insert を償却 $O(1)$、extract-min を償却 $O(\log C)$（$C$ はキーの最大値）で処理せよ。

入力形式

Q
query_1
...
query_Q

制約

$1 \le Q \le 2\times10^5$

$0 \le x \le 10^9$

単調性の制約が常に成立

クエリ1は空でも呼ばれうる（-1）

入出力例

入力例1

出力例1

入力例2

出力例2

-1
10

概念図

ヒント（段階的開示）

ヒント1（方向性）

Dijkstra法では、キューに入る値（暫定距離）は「今まで確定した最短距離の最小値」より小さくなることはない。この「一度出力した値より小さい値は二度と入らない」単調性は、二分ヒープでは使われずに捨てられている情報である。この情報を積極的に使えば、比較ソートの下限$O(\log N)$を回避できないか。

ヒント2（アプローチ）

キーの値を2進数で見て、「直前に出力した最小値$m$とのXORの最上位ビット位置」でバケツに分類する。$x$が$m$に近い（上位ビットが一致）ほど小さいバケツ番号に入る。異なるバケツ番号なら番号が小さい方が必ず値も小さい。extract-minはbucket0（$m$自身）があれば$O(1)$で取り出す。なければ最小の非空バケツを全部取り出し、その中の最小値を新しい基準にして再分配する。

ヒント3（誘導）

def bucket_index(x, m):
    d = x ^ m
    return d.bit_length()  # d=0 のとき0

def extract_min():
    if buckets[0]:
        return buckets[0].pop()
    k = 1
    while not buckets[k]:
        k += 1
    vals = buckets[k]; buckets[k] = []
    new_min = min(vals)
    for v in vals:
        buckets[bucket_index(v, new_min)].append(v)
    return buckets[0].pop()

再分配のコストは「あるバケツの要素がより小さい番号のバケツへ移る」ときだけ発生し、1要素が生涯に経験する番号減少の総和は高々$O(\log C)$回なので、全体で償却$O(Q\log C)$。

模範解答 (Python)

import sys


def main():
    data = sys.stdin.buffer.read().split()
    idx = 0
    Q = int(data[idx]); idx += 1

    BITS = 31  # 0 <= x <= 10^9 < 2^30 なので、XORの最大bit_lengthは31あれば十分
    NB = BITS + 2
    buckets = [[] for _ in range(NB)]

    last_min = 0
    has_extracted = False

    def bucket_index(x, m):
        d = x ^ m
        bl = d.bit_length()
        return bl if bl < NB else NB - 1

    def insert(x):
        b = bucket_index(x, last_min) if has_extracted else 0
        buckets[b].append(x)

    def extract_min():
        nonlocal last_min, has_extracted
        if buckets[0]:
            v = buckets[0].pop()
            last_min = v
            has_extracted = True
            return v
        k = 1
        while k < NB and not buckets[k]:
            k += 1
        if k == NB:
            return None
        vals = buckets[k]
        buckets[k] = []
        new_min = min(vals)
        last_min = new_min
        has_extracted = True
        for v in vals:
            b = bucket_index(v, new_min)
            buckets[b].append(v)
        v = buckets[0].pop()
        return v

    out = []
    for _ in range(Q):
        t = int(data[idx]); idx += 1
        if t == 0:
            x = int(data[idx]); idx += 1
            insert(x)
        else:
            r = extract_min()
            out.append("-1" if r is None else str(r))

    print("\n".join(out))


main()

Step-by-Step 解説

1バケツをXOR距離で定義する理由
$x,m$のXORの最上位ビット位置は「両者が2進表記でどこまで一致しているか」を表す。一致度が高いほどバケツ番号は小さい。$x=m$のときバケツ0。

2バケツ番号の単調性
基準値$m$は単調非減少かつ新規挿入は常に$m$以上。基準値が更新された後に再分類すると、バケツ番号は真に減少することはあっても増えることはない。

3extract-minの2ケース
bucket0があれば$O(1)$。なければ非0の最小番号バケツを線形探索し（$O(\log C)$）、その中身を新基準で再分配する。

4償却解析
1要素が生涯に再分配される回数はバケツ番号の真減少分だけ、つまり高々$O(\log C)$回。全体で$O(Q\log C)$。

5二分ヒープとの違い
基数ヒープは「非負整数」かつ「単調性」という前提のもとで、キーの値域$C$にのみ依存する$O(\log C)$を実現する。Dijkstra法では距離が単調非減少なのでこの前提が自然に満たされる。

よくあるミス

ミス	原因	正しい書き方
基準値last_minの更新を忘れる	bucket0から直接取り出すケースで更新を忘れる	bucket0から取り出す場合も必ずlast_minをその値に更新する
再分配後にbucket0が空になると誤解する	new_min=min(vals)なのでその要素は必ずXOR=0でbucket0に入ることに気づかない	new_minを再分配前バケツの最小値にすれば必ず1つはbucket0行きになる
単調性が保証されない場面でも使う	基数ヒープは一般の優先度付きキューの代替にはならない	単調性（Dijkstra的用途）が保証される場合のみ採用する
バケツ数を過小に確保する	C=10^9に対するビット数の見積もりを誤る	2^30>10^9なのでbit_lengthは最大31程度、安全側に余裕を持たせる
空キューでの例外	全バケツ空をチェックせずminを呼ぶ	全探索後k==NBなら-1(None)を返す分岐を明示する

次のステップ

発展: 本問の基数ヒープを使ってDijkstra法（非負整数重み、$V,E\le2\times10^5$）を実装し、二分ヒープ実装との実行時間を比較せよ。重みの最大値$C$が小さいほど効果が顕著になる。
発展2: バケツのサイズが偏るテストデータを設計し、償却計算量が理論通りであることを実測で確認せよ。

自己評価

完全理解おおむね理解要復習

Day 138-Q1 — 基数ヒープ（Radix Heap）

問題