Day 148-Q5 | Weak Heap（弱ヒープ・簡略版）

問題

$N$個の相異なる整数からなる配列$A[0..N-1]$が与えられる。次の規則で「弱ヒープ（簡略版）」を構築し、$Q$回の最小値取り出しクエリを処理せよ。

構築規則: インデックス$i$（$1\le i\le n-1$）の親を$p=\lfloor i/2\rfloor$とし、$i=n-1$から$1$まで降順に「$A[p]>A[i]$なら交換」を1回ずつ行う。これをちょうど$n-1$回行うと$A[0]$に全体の最小値が集まる。

クエリ処理: $A[0]$を出力して取り除き、$A[n-1]$を$A[0]$へ移してサイズを$n-1$に縮小、構築規則を全体に再適用する（簡略化のため部分再構築ではなく全体再構築を採用）。

$Q$回の取り出し結果を順に出力し、最後に初期構築とすべての再構築の比較回数の総和を出力せよ。

入力形式

N Q
A_0 A_1 ... A_{N-1}

制約

$1 \le Q \le N \le 100$

$A_i$は相異なる整数（$1\le A_i\le10^6$）

入出力例

入力例1

7 4
7 3 9 1 5 2 8

出力例1

初期構築6回＋再構築5,4,3,2回＝総比較回数20回。

概念図：降順走査で最小値が根に集まる（N=7の初期構築）

ヒント（段階的開示）

ヒント1（方向性）

通常のheapifyは「各ノードを下に沈める（複数回比較しうる）」が、弱ヒープは「各ノード$i$を親$p=i/2$とちょうど1回だけ比較する」線形走査で完結する。なぜ降順（$n-1$から$1$）に処理する必要があるかを考える。

ヒント2（アプローチ）

$i$を降順に処理するのは、処理する前に$i$より大きい添字はすでに処理済みで、$i$の子孫の最小値情報が$A[i]$に集約されているため。だから$A[p]$と$A[i]$の1回比較で部分木全体の最小値が確定する。

ヒント3（誘導）

def build(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n - 1, 0, -1):
        p = i // 2
        comparisons += 1
        if arr[p] > arr[i]:
            arr[p], arr[i] = arr[i], arr[p]
    return arr, comparisons

def extract_min_rebuild(arr):
    removed = arr[0]
    n = len(arr)
    new_arr = arr[:]
    new_arr[0] = new_arr[n - 1]
    new_arr = new_arr[:n - 1]
    new_arr, comps = build(new_arr)
    return removed, new_arr, comps

模範解答 (Python)

import sys

def build(arr):
    n = len(arr)
    comparisons = 0
    for i in range(n - 1, 0, -1):
        p = i // 2
        comparisons += 1
        if arr[p] > arr[i]:
            arr[p], arr[i] = arr[i], arr[p]
    return arr, comparisons


def extract_min_rebuild(arr):
    removed = arr[0]
    n = len(arr)
    if n == 1:
        return removed, [], 0
    new_arr = arr[:]
    new_arr[0] = new_arr[n - 1]
    new_arr = new_arr[:n - 1]
    new_arr, comps = build(new_arr)
    return removed, new_arr, comps


def main():
    data = sys.stdin.read().split()
    idx = 0
    N, Q = int(data[idx]), int(data[idx + 1]); idx += 2
    arr = [int(data[idx + i]) for i in range(N)]; idx += N

    arr, total = build(arr)
    outputs = []
    for _ in range(Q):
        removed, arr, comps = extract_min_rebuild(arr)
        outputs.append(removed)
        total += comps

    print('\n'.join(map(str, outputs)))
    print(total)


main()

Step-by-Step 解説

1降順走査だけで最小値が根に集まる理由
$i$を処理する時点で$i$より大きいすべての添字はすでに処理済み。だから$A[i]$には「$i$を根とする部分木の暫定最小値候補」が置かれている。

2比較回数がちょうど$N-1$回
$i=1,\dots,n-1$それぞれで1回しか比較しないため、初期構築の総比較回数は必ず$n-1$回。通常のheapifyより予測可能な回数である。

3取り出し後の再構築コスト
本問では全体再構築を採用しており$Q$回の取り出しで$O(N^2)$になる。真のWeak Heapは逆転フラグで管理された特別経路のみ辿り$O(\log N)$で再構築する。

4通常の二分ヒープとの比較
「1回の比較で必ず何かを確定させる」という設計思想が、より少ない比較回数でのヒープ構築を可能にしている。

よくあるミス

ミス	原因	正しい書き方
$i$を昇順に処理してしまう	降順でなければならない理由を見落とす	`range(n-1, 0, -1)`のように降順で処理する
親の添字を通常の二分木式にしてしまう	弱ヒープの親は$\lfloor i/2\rfloor$（0を除く）という規則を混同	`p = i // 2`を使う
取り出し後の再構築を省略してしまう	ヒープ性質が崩れたまま次のクエリに進む	縮小後の配列に必ず`build`を再実行する
比較回数を取り出し回数で数えてしまう	再構築の中で複数回の比較が発生することを見落とす	`build`が返す実際の比較回数（$n-1$個）を毎回加算する
$N=1$のケースでエラーになる	`range(0,0,-1)`が空になることを想定していない	$N=1$なら比較回数0、最小値はその1要素自身になることを確認する

次のステップ

発展: 逆転フラグ（reverse bit）による本来の$O(\log N)$のdistinguished path再構築を実装し、$N=10^5$規模のWeak Heapsortを完成させよ。
次回予告: MPM法に続く最大流応用の総復習、または新規テーマの探索。

自己評価

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

Day 148-Q5 — Weak Heap（弱ヒープ・簡略版・非対称マージによる最小比較回数構築）

問題