# 機能設計書 44-heapqueue

## 概要

本ドキュメントは、Nim標準ライブラリの`heapqueue`モジュールの機能設計について記述する。`heapqueue`は、二分ヒープ（Binary Heap）データ構造を実装し、優先度付きキュー（Priority Queue）として使用できるモジュールである。

### 本機能の処理概要

**業務上の目的・背景**：二分ヒープは、最小（または最大）要素への効率的なアクセスが必要なシナリオで不可欠なデータ構造である。`a[k] <= a[2*k+1]` かつ `a[k] <= a[2*k+2]` という特性により、常に最小要素が`a[0]`に配置される。配列ベースの実装により、連結リストベースの実装と比較してキャッシュ効率が高い。

**機能の利用シーン**：
- タスクスケジューリング：優先度に基づくタスク実行順序の管理
- Dijkstraアルゴリズム：グラフの最短経路探索
- イベント駆動シミュレーション：時系列イベントの管理
- ストリーム処理：Top-K問題、中央値の計算
- ハフマン符号化：最適なプレフィックスコードの構築
- A*探索アルゴリズム：ヒューリスティック探索

**主要な処理内容**：
1. 初期化（initHeapQueue, toHeapQueue）：空のヒープまたは配列からヒープを作成
2. 要素追加（push）：ヒープに要素を追加し、ヒープ特性を維持
3. 要素削除（pop）：最小要素を取り出し、ヒープ特性を維持
4. 要素参照（[]）：インデックスによる要素へのアクセス
5. 要素削除（del）：指定位置の要素を削除
6. 検索（find, contains）：要素の検索と存在確認
7. 複合操作（replace, pushpop）：効率的なpop+push/push+pop操作
8. クリア（clear）：全要素を削除

**関連システム・外部連携**：本モジュールは純粋なデータ構造ライブラリであり、外部システムとの直接連携はない。

**権限による制御**：該当なし（ライブラリモジュールのため）

## 関連画面

| 画面No | 画面名 | 関連種別 | 関連する操作・処理 |
|--------|--------|----------|------------------|
| - | - | - | 本モジュールはCLIライブラリのため画面関連なし |

## 機能種別

データ構造ライブラリ / コレクション操作 / 優先度付きキュー

## 入力仕様

### 入力パラメータ

| パラメータ名 | 型 | 必須 | 説明 | バリデーション |
|-------------|-----|-----|------|---------------|
| item | T | Yes（追加時） | 追加する要素 | `<`演算子が必要 |
| x | openArray[T] | Yes（変換時） | 変換元の配列 | - |
| index | Natural | Yes（del/[]時） | 要素のインデックス | - |

### 入力データソース

- プログラム内で生成されたHeapQueueインスタンス
- openArray（toHeapQueue使用時）

## 出力仕様

### 出力データ

| 項目名 | 型 | 説明 |
|--------|-----|------|
| result | HeapQueue[T] | 新規作成または変更されたヒープ |
| result | T | 最小要素（pop, replace, pushpop, []） |
| result | int | 要素数（len）、インデックス（find） |
| result | bool | 検索結果（contains） |
| result | string | 文字列表現（$） |

### 出力先

呼び出し元プログラムへの戻り値として返却

## 処理フロー

### 処理シーケンス

```
1. ヒープ初期化
   └─ initHeapQueue: 空のseqでHeapQueueを作成
   └─ toHeapQueue: 配列からO(n)でヒープを構築（heapify）

2. 要素追加（push）
   └─ 末尾に要素を追加
   └─ siftup: 親と比較し、必要に応じて上方向に移動

3. 要素削除（pop）
   └─ 最小要素（[0]）を返却
   └─ 末尾要素を先頭に移動
   └─ siftdownToBottom: 下方向に移動し、siftupで最終位置を決定

4. replace/pushpop（効率的な複合操作）
   └─ replace: pop+pushを1回のsiftdownで実行
   └─ pushpop: push+popを条件分岐で最適化
```

### フローチャート

```mermaid
flowchart TD
    A[HeapQueue操作] --> B{操作種別}
    B -->|push| C[末尾に追加]
    B -->|pop| D[先頭要素を返却]
    B -->|replace| E[先頭を置換]
    B -->|pushpop| F{item < heap[0]?}
    C --> G[siftup: 上方向調整]
    D --> H[末尾を先頭に移動]
    H --> I[siftdownToBottom: 下方向調整]
    E --> J[siftdown: 下方向調整]
    F -->|Yes| K[itemを返却]
    F -->|No| L[swap後siftdown]
    G --> M[ヒープ特性維持]
    I --> M
    J --> M
```

## ビジネスルール

### 業務ルール

| ルールNo | ルール名 | 内容 | 適用条件 |
|---------|---------|------|---------|
| BR-01 | 最小ヒープ | 常に最小要素がheap[0]に配置される | 常時 |
| BR-02 | 比較演算子必須 | 要素型Tには`<`演算子が必要 | 常時 |
| BR-03 | ヒープ特性 | a[k] <= a[2*k+1] かつ a[k] <= a[2*k+2] | 常時 |
| BR-04 | 線形時間構築 | toHeapQueueはO(n)でヒープを構築 | toHeapQueue使用時 |
| BR-05 | イテレーション中変更禁止 | items使用中にヒープの長さを変更するとassertエラー | items使用時 |

### 計算ロジック

- **siftup**: 親インデックス = `(pos - 1) shr 1`、子が親より小さければ交換して上方へ
- **siftdown**: 左子 = `2*pos + 1`、右子 = `2*pos + 2`、より小さい子と交換して下方へ
- **siftdownToBottom**: 末尾まで下降後、siftupで最終位置決定（削除に最適化）
- **heapify（toHeapQueue）**: 後半ノードから順にsiftdownを適用

## データベース操作仕様

### 操作別データベース影響一覧

| 操作 | 対象テーブル | 操作種別 | 概要 |
|-----|-------------|---------|------|
| - | - | - | 本モジュールはデータベース操作を行わない |

## エラー処理

### エラーケース一覧

| エラーコード | エラー種別 | 発生条件 | 対処方法 |
|------------|----------|---------|---------|
| IndexDefect | 範囲エラー | 空ヒープに対するpop操作（暗黙的） | 事前にlen > 0を確認 |
| AssertionDefect | アサーション | items中にヒープの長さを変更 | イテレーション中は構造を変更しない |

### リトライ仕様

該当なし（同期処理のためリトライ不要）

## トランザクション仕様

該当なし（データベース操作なし）

## パフォーマンス要件

- **push**: O(log n)の時間計算量
- **pop**: O(log n)の時間計算量
- **replace**: O(log n)の時間計算量（pop + pushより効率的）
- **pushpop**: O(log n)の時間計算量（push + popより効率的）
- **toHeapQueue**: O(n)の時間計算量（配列からのヒープ構築）
- **find/contains**: O(n)の時間計算量（線形探索）
- **del**: O(log n)の時間計算量
- **空間計算量**: O(n)

## セキュリティ考慮事項

- 本モジュールはメモリ安全性を保証
- 内部的にseq[T]を使用するためGCにより管理される
- sink parameterによりmove semanticsをサポート

## 備考

- Nim 1.3以降で追加された機能（toHeapQueue, find等）には`since`プラグマが付与
- Nim 2.1.1以降で追加されたitems/containsイテレータも存在
- カスタムオブジェクトを使用する場合は`<`演算子を実装する必要がある

---

## コードリーディングガイド

本機能を理解するために参照すべきファイルと、推奨する読み解き順序を以下に示す。

### 推奨読解順序

#### Step 1: データ構造とヒープ特性を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 1-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 10-46行目: モジュールドキュメントと使用例 |
| 1-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 53-55行目: HeapQueue型定義 |

**読解のコツ**:
- **10-15行目**: 二分ヒープの特性（a[k] <= a[2*k+1] かつ a[k] <= a[2*k+2]）
- **32-33行目**: カスタムオブジェクトには`<`演算子が必要
- **53-55行目**: HeapQueue[T]は内部的にseq[T]をdataフィールドとして持つ

#### Step 2: 基本操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 2-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 57-65行目: initHeapQueue |
| 2-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 67-84行目: len, [], items |

**主要処理フロー**:
- **57-65行目**: initHeapQueue - default()で空のHeapQueueを返却
- **67-73行目**: len - data.lenを返却
- **75-77行目**: [] - data[i]への直接アクセス
- **79-84行目**: items - L保存してイテレーション、長さ変更検出付き

#### Step 3: siftup/siftdown操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 3-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 86-86行目: heapCmp |
| 3-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 88-104行目: siftup |
| 3-3 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 106-126行目: siftdownToBottom |
| 3-4 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 128-142行目: siftdown |

**主要処理フロー**:
- **86行目**: heapCmp - `x < y`を返却
- **88-104行目**: siftup - 親インデックス = `(pos - 1) shr 1`、親より小さければ交換して上方へ
- **106-126行目**: siftdownToBottom - 末尾まで下降、最後にsiftupで最終位置決定
- **128-142行目**: siftdown - 子と比較し、必要に応じて下降（replace用）

**注意点**:
- siftdownToBottom（106-126行目）は要素がヒープの底近くになると予想される場合に最適化されている

#### Step 4: push/pop操作を理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 4-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 144-147行目: push |
| 4-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 164-177行目: pop |

**主要処理フロー**:
- **144-147行目**: push - data.add(item)後にsiftup(0, len-1)
- **164-177行目**: pop - 末尾要素をpop、先頭と交換してsiftdownToBottom

#### Step 5: toHeapQueueを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 5-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 149-162行目: toHeapQueue |

**主要処理フロー**:
- **159-162行目**: ヒープ構築 - @xでseq化し、後半ノードから順にsiftdownを適用
- **161行目**: countdown(x.len div 2 - 1, 0) - 非葉ノードのみ処理（O(n)構築）

#### Step 6: find/contains/delを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 6-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 179-189行目: find |
| 6-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 191-194行目: contains |
| 6-3 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 196-208行目: del |

**主要処理フロー**:
- **179-189行目**: find - 線形探索でインデックスを返却（見つからなければ-1）
- **191-194行目**: contains - find >= 0を返却
- **196-208行目**: del - 末尾と交換後siftdownToBottom

#### Step 7: replace/pushpop/clearを理解する

| 順序 | ファイル | パス | 読解ポイント |
|-----|---------|------|-------------|
| 7-1 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 210-228行目: replace |
| 7-2 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 230-245行目: pushpop |
| 7-3 | heapqueue.nim | `lib/pure/collections/heapqueue.nim` | 247-254行目: clear |

**主要処理フロー**:
- **210-228行目**: replace - heap[0]を返却し、新要素を置いてsiftdown
- **230-245行目**: pushpop - item < heap[0]ならそのまま返却、そうでなければswapしてsiftdown
- **247-254行目**: clear - data.setLen(0)

### プログラム呼び出し階層図

```
heapqueue.nim (ユーザーコード)
    │
    ├─ 初期化
    │   ├─ initHeapQueue() → default(HeapQueue[T])
    │   └─ toHeapQueue(openArray) → @x + countdown siftdown (O(n))
    │
    ├─ 追加操作
    │   └─ push(item) → data.add(item) → siftup(0, len-1)
    │
    ├─ 削除操作
    │   ├─ pop() → data.pop() → swap → siftdownToBottom(0)
    │   └─ del(index) → swap(data[^1], data[index]) → siftdownToBottom(index)
    │
    ├─ 複合操作
    │   ├─ replace(item) → return heap[0] → heap[0]=item → siftdown(0)
    │   └─ pushpop(item) → if item >= heap[0]: swap → siftdown(0)
    │
    └─ ヒープ調整（内部）
        ├─ siftup(startpos, pos) → 親方向に上昇
        ├─ siftdown(pos) → 子方向に下降
        └─ siftdownToBottom(pos) → 末尾まで下降 → siftup
```

### データフロー図

```
[入力]                      [処理]                           [出力]

openArray[T] ──────────▶ toHeapQueue ────────────────────▶ HeapQueue[T]
                              │
                    ┌─────────▼─────────┐
                    │  HeapQueue[T]     │
                    │  ┌─────────────┐  │
                    │  │ data: seq[T]│  │
                    │  │  [0] = min  │  │
                    │  │  [1]  [2]   │  │──────▶ T (pop/replace)
                    │  │ [3][4][5][6]│  │
                    │  └─────────────┘  │──────▶ int (len/find)
                    │                   │
                    │  二分ヒープ構造    │──────▶ bool (contains)
                    └───────────────────┘
                              │
                              ▼
              ヒープ特性: a[k] <= a[2k+1], a[k] <= a[2k+2]

push操作:
    item ───▶ data.add ───▶ siftup ───▶ ヒープ特性維持

pop操作:
    heap[0] ◀─── data.pop ───▶ swap(head, last) ───▶ siftdownToBottom
```

### 関連ファイル一覧

| ファイル | パス | 種別 | 役割 |
|---------|------|------|------|
| heapqueue.nim | `lib/pure/collections/heapqueue.nim` | ソース | メインモジュール（全機能実装） |
| since.nim | `lib/std/private/since.nim` | ソース | バージョン管理プラグマ |
| assertions.nim | `lib/std/assertions.nim` | ソース | assert機能を提供 |
