スタック・キュー・ヒープ・ハッシュ表：目的と操作量、償却と最悪の区別
基本データ構造が「何を速くしたいか」で設計されていることを理解し、操作量の見積もり方と、償却計算量と最悪計算量の違いを小さな数値例で確認する。
- スタック・キュー・ヒープ・ハッシュ表それぞれが得意とする操作と、その操作量（オーダー）を説明できる
- 動的配列の末尾追加のように、まれに遅くなる操作を含めて平均コストを考える「償却解析」の考え方を使える
- 償却計算量が良くても最悪計算量が悪い場合があることを、ハッシュ表や動的配列の具体例で区別して説明できる
📑 目次
1．データ構造は「どの操作を速くするか」で選ぶ
同じデータを覚えておくにも、後でどの操作を何回行うかによって向き不向きがあります。ここでは操作量を「データ件数 n に対して、基本操作（比較・代入・参照）がだいたい何回起こるか」で表し、定数倍を無視して O(1)、O(log n)、O(n) のように書きます。O(1) は件数によらずほぼ一定、O(log n) は件数が1000倍になっても操作回数は約10倍程度、O(n) は件数に比例して増える、という意味です。以下の操作量は、このレッスンで扱う標準的な実装（配列によるスタック・キュー、二分ヒープ、チェイン法のハッシュ表、末尾追加の動的配列）についての目安で、実装やライブラリによって条件が変わることがあります。
| 構造 | 得意な操作 | 操作量の目安 | 特徴・注意 |
|---|---|---|---|
| スタック | push（積む）・pop（取り出す） | O(1) | 最後に積んだものから出る（LIFO） |
| キュー | enqueue（追加）・dequeue（取り出し） | O(1) | 先に入れたものから出る（FIFO）。循環配列で O(1) を保つ |
| 二分ヒープ | 最小値（または最大値）の取得・挿入 | 取得 O(1)、挿入・削除 O(log n) | 完全二分木なので木の高さは約 log₂n |
| ハッシュ表 | キーによる検索・挿入・削除 | 平均 O(1)、最悪 O(n) | ハッシュの衝突が続くと同一連鎖内を順に調べる |
| 動的配列 | 末尾への追加、インデックス参照 | 追加は償却 O(1)、参照 O(1) | 容量が尽きると再配置に O(n) かかる（第6節） |
2．スタック：最後に入れたものを最初に取り出す
スタックは、データを一枚ずつ皿を積むように並べ、取り出しは必ず最後に積んだものから行う構造です（LIFO: Last In, First Out）。操作は push（上に積む）と pop（上から取り出す）で、どちらも配列の末尾を使えば位置の計算と1件の代入だけで済むため O(1) です。途中の要素を飛ばして取り出すことはできません。それが制限であり、同時にそれが利点です。「もっとも最近の出来事から順に処理する」場面、たとえば元に戻す操作の履歴や、関数呼び出しの戻り番地の管理（呼び出しスタック）に合致します。
文字列 "({[()]})" の括弧の対応が取れているか、スタックで確認する手順を追おう。開き括弧は push、閉じ括弧は「スタックの先頭と種類が一致すれば pop」とします。
解答・解説
左から順に見ると、( { [ でスタックは下から ( { [ となる。次の ) は先頭 [ と種類が違うので**ここで対応が取れていない**と分かる。このように「待っている開き括弧」をスタックに積んでおけば、閉じ括弧が現れた瞬間に一致判定ができ、文字列を一度走査するだけで O(n) で確認できます。対応が取れる入力の場合も、終了時にスタックが空であることを確認するのが手順の一部です。
括弧の例は、スタックが「途中の状態を覚えておき、必要になったら最近のものから取り出す」役割に適していることを示しています。もし「先に入れたものから順に取り出したい」のであれば、同じ配列でも向きが逆の構造、キューが必要になります。
3．キュー：先に入れたものを最初に取り出す
キューは待ち行列です。enqueue で末尾に追加し、dequeue で先頭から取り出します（FIFO: First In, First Out）。単純な配列で先頭の要素を取り出すたびに残りを詰め直すと1回あたり O(n) かかりますが、先頭位置と末尾位置を覚えておく循環配列にすれば、要素の移動をせずに両操作を O(1) にできます。配列の末尾が埋まったら先頭に戻るよう、位置は「(現在位置 + 1) を容量で割った余り」で計算します。
容量4の循環配列に、enqueue(A) → enqueue(B) → dequeue → enqueue(C) → dequeue → dequeue をこの順で行う。各時点の配列の中身（先頭から順）を答えよ。
解答・解説
① A を位置0へ → [A, , , ]。② B を位置1へ → [A, B, , ]。③ dequeue で先頭 A を取り出し先頭は位置1 → [_, B, , ]。④ C を位置2へ → [_, B, C, ]。⑤ dequeue で B を取り出し先頭は位置2 → [_, _, C, ]。⑥ dequeue で C を取り出し先頭は位置3、キューは空。このように要素を動かさずに「先頭と末尾の位置」だけが進むため、各操作は件数 n によらず O(1) で済みます。
4．ヒープ：もっとも小さい（大きい）ものをいつでもすぐ取り出す
ヒープは「親は子以下（最小ヒープの場合）」という順序制約を満たす完全二分木です。子同士の順序は問わないため「完全に整列」してはいませんが、最小値が必ず根にあることが保証されます。n 個のデータの完全二分木の高さは約 log₂ n なので、根から下へ比較しながら入れ替える操作（下降ヒープ化）は各段で定数回、合計で高さに比例する回数の比較を行い、O(log n) で済みます。挿入も同様に、末尾に置いて親と比較しながら上がる操作（上昇ヒープ化）で O(log n) です。
🔍 高さが約 log₂ n になる理由
- 完全二分木の最下段より上は埋まっている
根の高さを0とします。高さhの最下段には少なくとも1個あり、それより上には2^h−1個あります。
- 高さの上下限を合わせる
n≥1で成立。n=1000なら高さは9です。高さの下限だけでは操作量の上限を証明できません。
- 各段で定数回の比較
下降時は小さい方の子を選ぶ比較と親との比較が必要です。挿入時は各段で親との比較を行います。
最小ヒープ [3, 7, 5, 9, 12, 6]（配列を上から・左から並べたもの）に 2 を挿入した後のヒープを配列で答えよ。
解答・解説
2 を末尾（位置6）に置く → [3,7,5,9,12,6,2]。親は位置 floor((6−1)/2)=2 の 5。5>2 なので交換 → [3,7,2,9,12,6,5]。次の親は位置 floor((2−1)/2)=0 の 3。3>2 なので交換 → [2,7,3,9,12,6,5]。根に到達したので終了。すべての親≤子の制約を満たす（7≥2、3≥2、9≥7、12≥7、6≥3、5≥3）。挿入の比較は2回で済みました。一般には高さ分だけ比較しうるので O(log n) です。
5．ハッシュ表：キーから直接場所を計算する
配列の参照が O(1) であるのは「インデックスから場所が直接計算できる」からです。ハッシュ表はこれを応用し、キーをハッシュ関数で配列のインデックスに変換して格納します。ハッシュ値が異なるキー同士で重なる（衝突）ことがあるため、チェイン法では同じインデックスに連鎖（リスト）で複数の要素を保持します。ハッシュがキーに対してよく分散していれば、連鎖の長さは要素数を容量で割った負荷率（load factor）α = n / 容量 にほぼ比例し、α を小さく保てば平均 O(1) です。
ただしこの O(1) は平均（期待値）の評価で、その根拠はハッシュ値が偏らず分散するという仮定です。逆に、最悪の場合（たとえば容量を単純な余りで決めていて、すべてのキーが同じ余りになる場合）は、全要素が一つの連鎖に集まり、検索は連鎖を先頭から順に調べるので O(n) になります。ここが第7節で述べる「償却でも最悪でもない、平均の保証」の典型的な例です。
容量10のハッシュ表に、ハッシュ値が「キーの数値を10で割った余り」である架空のキー 11, 21, 31, 42, 5 をこの順に挿入する。① 各インデックスの連鎖の内容、② 負荷率、③ キー 31 の検索で比較する要素数を答えよ。
解答・解説
① 11,21,31 はすべて余り1 → インデックス1の連鎖は [11, 21, 31]。42 は余り2 → [42]。5 は余り5 → [5]。② n=5、容量10で負荷率 α=0.5。③ キー31のハッシュ値は1で、インデックス1の連鎖を先頭から順に見るため 11、21 と比較して3回目で見つかります。もし 11,21,31,41,51 のように余り1のキーが集中すれば連鎖の長さは5で、検索は O(n) に近づきます。このとき負荷率は 5/10=0.5 と同じでも、**分散のしかた**が違うため平均的な評価が破綻することに注意してください。
6．償却解析：まれに重い操作を含めた平均コスト
動的配列への末尾追加は、普通は O(1) ですが、容量が尽きた瞬間だけ、より大きな配列を新たに確保して全要素をコピーするので O(n) かかります。それでも「1回あたりのコスト」を平均して考えるのが償却解析です。ポイントは、重い操作の前後に軽い操作が十分多くあることを保証する設計になっていることです。容量を2倍にする戦略では、容量 C/2 から C へ拡大した後、次の拡大までには C/2 回の追加が必要です。その間の追加に定数ずつ費用を配分すれば、次のコピー費用 C を賄えます。
🔍 容量2倍戦略で、合計コピー量を上限評価する
- 最終容量を C=2^k とする
初期容量1で空から追加します。k=0ならコピー数は0。容量Cに拡大する直前のコピー量はC/2です。
- n 回の追加を終えた時点でのコピー総数
n≥1。総コピー数が常にn未満になるわけではありません。たとえばn=9では15個をコピーします。
- 1回の追加あたりの平均
- 結論：償却 O(1)
通常の代入コスト O(1) に、コピーの平均2回分以下を足しても定数です。
初期容量1、容量が尽きたら2倍にする動的配列に、8回の末尾追加を行う。① 容量が尽きて全コピーが起こるのは何回目の追加か（容量が満杯の状態への追加を「コピーの発生する追加」と呼ぶ）。② 合計コピー数と1回あたりの平均コピー数を答えよ。
解答・解説
初期容量1。① 2回目の追加（容量1が満杯→容量2へ）、3回目（容量2満杯→容量4へ）、5回目（容量4満杯→容量8へ）の計3回でコピーが起こります。② 各コピーで移す要素数は1、2、4個で合計7個。8回の追加に対し 7/8 = 0.875 回/追加で、上限2を下回っています。この例ではコピー総数はn未満ですが、一般の保証は2n未満です。n=9では15個をコピーするのでn未満とはいえません。
7．償却と最悪の違い：何が保証されるか
償却計算量と最悪計算量は、保証の範囲が違います。償却 O(1) は「十分多くの操作をまとめて見れば平均して定数回」という保証で、個々の1操作が常に定数時間であることまで約束しません。最悪 O(1) は「どんな入力・どんなタイミングでも、1操作が定数時間以内」という保証です。
| 操作・構造 | 償却・平均の評価 | 最悪の評価 | 評価の根拠 |
|---|---|---|---|
| 動的配列の末尾追加 | 償却 O(1) | O(n) | 倍増戦略でコピーがまれにしか起こらないこと（第6節） |
| ハッシュ表（チェイン法）の検索 | 平均 O(1) | O(n) | ハッシュがよく分散するという確率的仮定（第5節） |
| スタック・キューの push/pop, enqueue/dequeue | O(1) | O(1) | 位置の計算と1件の代入・参照だけで完結するため |
| ヒープの挿入・根の削除 | O(log n) | O(log n) | 完全二分木の高さが約 log₂ n に上限づけられるため |
注意が必要なのは2点です。第一に、ハッシュ表の「平均 O(1)」は償却とも最悪でもなく、ハッシュ値の分散という確率的な仮定に依存する評価です。第二に、動的配列の「償却 O(1)」は保証が弱い代わりに、実際には平均的に速いという実用上の利点があります。逆に、リアルタイム性（どの1操作も遅延が許されない処理）が求められる場面では、償却 O(1) の構造のまれに重い操作が問題になることがあり、その場合は最初から容量を確保しておく、最悪 O(log n) の平衡探索木を使う、といった選択が現実のシステムで行われます。
次のa〜dの処理に最も自然なデータ構造を、スタック・キュー・二分ヒープ・ハッシュ表から選び、理由を1文ずつ添えよ。 a. 打ち間違えた入力を直前のものから順に取り消す。 b. 受付順に順番札を配り、順番が来たら先頭の札を呼び出す。 c. 1000件の検索結果から毎回もっとも優先度の高い1件を取り出す。 d. 会員ID（整数）から名前を、IDを指定してすぐに参照する。
解答・解説
a. スタック（LIFO）—「最近の出来事から順に」という要求がそのままスタックの取り出し順序です。b. キュー（FIFO）—受付順の公平な処理は先頭から取り出すキューの動作と一致します。c. ヒープ（優先度付きキュー）—最小（または最大）値の参照が O(1)、取り出して削除する操作と再挿入が O(log n) で済み、1000件を毎回ソートする O(n log n) と比べて効率的です。d. ハッシュ表—キーからインデックスを直接計算でき、平均 O(1) で参照できるためです（IDの分散が悪く衝突が続く場合は性能が落ちる点は第5節のとおり）。
練習：操作量と評価の種類を見分ける
容量16・要素数12のハッシュ表（チェイン法）の負荷率を求め、負荷率が大きくなると平均検索時間がどう変化するか、理由とともに答えよう。
解答・解説
負荷率 α = 12/16 = 0.75。負荷率が大きくなると1つのインデックスに平均してより多くの要素が入るため連鎖の長さが伸び、検索で連鎖内を順に比較する回数が増えます。平均検索時間は負荷率にほぼ比例して悪化します（ハッシュの分散が良い場合の目安）。実際のライブラリでは、負荷率がしきい値（例：0.75）を超えたら容量を増やす再ハッシュを行うことがあります。
最小ヒープ [2, 5, 4, 9, 7, 6] から根の要素 2 を取り除いた後、最後の要素 6 を根に移して下降ヒープ化した後の配列を答えよう。
解答・解説
2 を除き、最後の要素 6 を根に置く → [6,5,4,9,7]。子は5と4で小さい方4を比較 → 6>4 なので交換 → [4,5,6,9,7]。位置2の子はもうないので終了。すべての親≤子を満たします（5≥4、6≥4、9≥5、7≥5）。比較回数は2回で、一般には高さ O(log n) 回です。
次のうち、最悪 O(1) とは言えないものをすべて選び、理由を答えよう。(ア) 循環配列キューの enqueue (イ) 動的配列の末尾追加（償却 O(1)）(ウ) 二分ヒープの最小値の取得（根の値を見るだけ）(エ) ハッシュ表の検索（平均 O(1)）
解答・解説
イとエ。(イ) は容量が尽きたときに全要素のコピー O(n) が必要で、1回の操作としては O(n) の可能性があります（平均としては償却 O(1)）。(エ) はすべてのキーが同じ連鎖に入ると最悪 O(n) になりえます。(ア) は位置の計算と1件の代入のみで最悪 O(1)。(ウ) は根を参照するだけで最悪 O(1) です。
動的配列（初期容量1、容量を2倍にする）に15回の末尾追加を行うとき、①全コピーが起こる追加の回数、②合計コピー数、③1回あたりの平均コピー数を答え、償却 O(1) と評価できるかを述べよう。
解答・解説
① 容量1→2→4→8→16 で、2回目・3回目・5回目・9回目の追加の計4回でコピーが起こります。② 移す要素数は1+2+4+8=15個。③ 15/15=1回/追加。一般に n 回の追加でコピー総数は 2n 未満で、1回あたり2回未満に収まるため、償却 O(1) と評価できます。
問1. スタックとキューの取り出し順序の違いとして正しいものはどれか。
問2. 容量を2倍にする動的配列で「償却 O(1)」と言える根拠はどれか。
問3. ハッシュ表の検索が「平均 O(1)、最悪 O(n)」となる理由として正しいものはどれか。
問4. 「どの1操作も遅延が許されない」リアルタイム処理で、償却 O(1) の構造を避ける理由はどれか。
問5. n=1000 件の二分ヒープへの挿入で、比較回数の上限はおよそいくらか（高さの計算に基づく）。