二分ヒープの親インデックス
ノードの添字と番号の付け方を選びます。0始まりのヒープでは、4を2で割って切り捨てると2なので、添字5の親は2です。根には親がないため、架空の位置を作らずに受け付けません。ブラウザで無料で使えます。
- 無料
- ブラウザで動作
- 登録不要
- データは端末の外に出ません
無料で実行
計算例
- 添字
- 5
- インデックス方式
- Zero
- 親
- 2
- 根
- 0
配列に置いた二分ヒープは、優先度付きキュー、ヒープソート、多くの最短路実装の土台です。教科書はどれも親の式を載せますが、二つの添字規約は一つずれ、そのオフバイワンがサイレントに sift-up を壊します。この親インデックス計算機は、節点の配列添字と番号付け規約（根が添字ゼロのゼロ始まり、または根が添字一のイチ始まり）を受け取り、対応する閉形式で親を返します。ゼロ始まりでは親は添字から一を引いて二で割った床です。イチ始まりでは親は添字を二で割った床です。根には親がなく、負やダミーの枠を作らず拒否します。
ゼロ始まりとイチ始まりの親の式
配列に並べた二分ヒープは、親や子へのポインタを決して持ちません。節点から親への歩きは閉形式の添字式であり、その式は配列をゼロから数えるか一から数えるかで変わります。
C、Java、JavaScript、Python、および本番の大半のヒープが使うゼロ始まりでは、根は添字ゼロ、節点 i の子は二 i 足す一と二 i 足す二、根以外の親は i から一を引いて二で割った床です。多くの教科書、CLRS 風疑似コード、競技テンプレートが使うイチ始まりでは、根は添字一、子は二 i と二 i 足す一、親は単に i を二で割った床です。
どちらの恒等式も整数添字では厳密であり、近似でも入れ替え可能でもありません。本計算機は規約を選んだあとに対応する恒等式を適用し、根には親がないため根を拒否します。二つの規約を混同するのが典型的なオフバイワンです。
言語の配列をイチ始まりとして扱う、あるいは教科書の図をゼロ始まりとして扱うと、親が真実から一つずれ、sift-up と decrease-key が静かに壊れます。
入力契約・応答の形・エラーの扱い
親を知りたい節点の配列枠を示す有限整数です。indexing は任意で既定は zero、つまり根が添字ゼロのゼロ始まり配列です。ヒープが一から数えるときは one を送ってください。
indexing が zero のとき添字は少なくともゼロ、one のとき少なくとも一でなければなりません。選んだ規約の根（ゼロ始まりではゼロ、イチ始まりでは一）は、その根を名指しするメッセージで拒否します。マイナス一の親を捏造したり末尾へ巻き戻したりするのは嘘になるからです。
例: 既定のゼロ始まりで添字五なら親は二です。四を二で割った床が二だからです。例: イチ始まりで添字四なら親は二ですが、同じ四をゼロ始まりにすると親は一です。
検証失敗は課金されません。
親インデックス計算機が役立つ場面
面接対策、アルゴリズム講義、本番の優先度付きキューは同じ親への歩きを必要とし、しかも番号付けでは意見が割れます。sift-up の跡を追う学習者は、言語配列では五の親が二であること、イチ始まりの用紙では四の親が二であることを、毎回手で式をひっくり返さずに確かめたいのです。
データ構造の宿題用オートグレーダは、根を親なしとして拒否する決定的オラクルを必要とし、欠陥提出が成功と誤認しうる無言のマイナス一を返しません。教科書のヒープをゼロ始まり言語へ移植する技術者、あるいはその逆は、両方の規約をテストに固定し、出荷前にオフバイワンを捕まえられます。
配列から木を描く可視化や競技足場は、根以外の各枠の親を尋ね、式の写しを二つ埋め込まずに辺を置けます。要求を小さく保ち親の整数をテストに固定すれば、自前のヒープライブラリを立てずに宿題、LMS プラグイン、エッジワーカー向けの再現可能な歩きが得られます。
活用例
宿題と面接のトレース
sift-up やヒープソートを辿りながら任意の配列枠の親を確認し、教科書のイチ始まりと言語配列のゼロ始まりを切り替えられます。
自動採点と競技オラクル
根を親なしとして拒否する決定的な親の式でヒープ添字の設問を採点し、ダミー添字を捏造しません。
規約をまたぐヒープの移植
イチ始まりの CLRS 風疑似コードをゼロ始まりの言語配列へ、あるいはその逆へ移すとき、オフバイワンが出荷される前に親の歩きをテストへ固定します。
よくある質問
二分ヒープ配列で節点の親はどう求めますか？
ゼロ始まりでは親は floor((index − 1) / 2) です。イチ始まりでは親は floor(index / 2) です。
ヒープのゼロ始まりとイチ始まりはどう違いますか？
ゼロ始まりは根を添字 0 に置き parent = floor((i − 1) / 2) を使います。イチ始まりは根を添字 1 に置き parent = floor(i / 2) を使います。同じ数値でも規約が違えば親が変わり得ます。
根の親を尋ねるとどうなりますか？
根（indexing が zero なら添字 0、one なら添字 1）には親がなく、計算機は親を捏造しません。
ゼロ始まりの二分ヒープで添字 5 の親は何ですか？
二です。 floor((5 − 1) / 2) = 2。イチ始まりでも同じ添字は 2 ですが、4 が分岐する対です。ゼロ始まりなら親 1、イチ始まりなら親 2 です。
親の式で1つずれると何が問題ですか？
結果は本当の親のすぐ隣にある実在の位置なので、エラーにはなりません。その代わり、要素を上へ移す処理や優先度を下げる処理が間違った要素を比べて入れ替え、ヒープの順序が気づかないうちに崩れます。
関連ツール
開発者向け — APIアクセス
このページの機能はすべてAPIからも利用できます。自社システムに組み込みたいチーム向けのセクションです。それ以外の方は上のツールをそのままお使いください。
エンドポイント
Bearerトークンで認証し、POST1回でタスクをキューに登録します。結果はWebhookまたは署名付きリンクで受け取れます。
お使いのスタックから呼び出す
curl -X POST https://api.kit.forhosting.com/dev/heap-parent-index \
-H "Authorization: Bearer $KIT_KEY" \
-H "Content-Type: application/json" \
-d '{"index":5}'const res = await fetch("https://api.kit.forhosting.com/dev/heap-parent-index", {
method: "POST",
headers: {
"Authorization": `Bearer ${process.env.KIT_KEY}`,
"Content-Type": "application/json"
},
body: JSON.stringify({
"index": 5
})
});
const { task_id } = await res.json();import os, requests
res = requests.post(
"https://api.kit.forhosting.com/dev/heap-parent-index",
headers={"Authorization": f"Bearer {os.environ['KIT_KEY']}"},
json={
"index": 5
},
)
task_id = res.json()["task_id"]<?php
$res = file_get_contents("https://api.kit.forhosting.com/dev/heap-parent-index", false, stream_context_create([
"http" => [
"method" => "POST",
"header" => "Authorization: Bearer " . getenv("KIT_KEY") . "\r\nContent-Type: application/json",
"content" => '{"index":5}',
],
]));
$task = json_decode($res, true);body := bytes.NewBufferString(`{"index":5}`)
req, _ := http.NewRequest("POST", "https://api.kit.forhosting.com/dev/heap-parent-index", body)
req.Header.Set("Authorization", "Bearer "+os.Getenv("KIT_KEY"))
req.Header.Set("Content-Type", "application/json")
res, _ := http.DefaultClient.Do(req)リクエスト例
{
"index": 5
}レスポンス例
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.heap_parent_index",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}非同期APIです。task_idは即時に返ります。ポーリングは1秒あたり1リクエストまでです。
料金
単価はすべて公開しています。トークン換算や独自クレジットはありません。失敗したタスクは課金されません。
エラー
| HTTP | コード | 意味 |
|---|---|---|
401 | unauthorized | APIキーが無効か、指定されていません。Authorizationヘッダーを確認してください。 |
402 | insufficient_balance | 残高が不足しています。チャージ後に再度お試しください。 |
404 | unknown_type | 指定されたタスクタイプは存在しません。タイプ名を確認してください。 |
429 | rate_limited | リクエストが多すぎます。しばらく待ってから再度お試しください。 |
技術的な注記
ゼロ始まりとイチ始まりの親の式
応答は送った添字と規約をエコーし、親を名付け、その規約の根の添字を名付け、答えの横に印刷できる文字列として式を再掲し、成功した歩きでは is_root を false にして、成功を「実在する親がある」と扱えるようにします。
入力契約・応答の形・エラーの扱い
POST する JSON 本体では index が必須です。index の別名として i と node、indexing の別名として convention を受け付けるため、講義ノートからコピーした断片も解析できます。非有限値、真偽値、空文字列、欠落した index は invalid_input で失敗します。安全な整数上限を超える添字は、床除算の下で JSON 数値が正確であり続けるよう拒否します。成功時の本体にはエコーした index と indexing、計算した整数の parent、false の is_root、規約の根枠である root、および「親は開き括弧 添字マイナス一 閉じ括弧 を二で割った床」または「親は添字を二で割った床」という formula が含まれます。その対こそ規約がフィールドである理由です。
親インデックス計算機が役立つ場面
parse の A 段階のため、成功する呼び出しはモデルトークンも外向きネットもなく公開の基本料金 $0.002 であり、無効入力は残高を消費しません。
技術的な質問
二分ヒープの親インデックス計算機の料金は。
ブラウザの道具は無料です。API 要求は成功した呼び出しごとに前払い KIT 残高から $0.002 です。無効入力は課金されません。