Indice parent d'un tas binaire
Dans un tas numéroté depuis 0, l'indice 5 a son parent en 2, car la partie entière de 4 divisé par 2 vaut 2. La racine n'a pas de parent : elle est refusée plutôt que dotée d'une case inventée. Gratuit dans votre navigateur.
- Gratuit
- Fonctionne dans votre navigateur
- Sans inscription
- Vos données restent sur votre appareil
Lancer gratuitement
Exemple résolu
- Indice
- 5
- Indexation
- Zero
- Parent
- 2
- Racine
- 0
Un tas binaire stocké dans un tableau est la structure derrière les files de priorité, le heapsort et bien des plus courts chemins. Chaque manuel donne une formule du parent, mais les deux conventions de numérotation divergent d'une unité, et un décalage d'un corrompt en silence le sift-up. Ce calculateur d'indice parent accepte l'indice de tableau d'un nœud et la convention de numérotation — à partir de zéro, racine à l'indice zéro, ou à partir de un, racine à l'indice un — et renvoie le parent par la forme fermée correspondante. Les tas indexés à partir de zéro utilisent parent égal au plancher de l'indice moins un sur deux. Les tas indexés à partir de un utilisent parent égal au plancher de l'indice sur deux. La racine n'a pas de parent et est refusée plutôt que d'inventer une case négative ou fictive.
Formules du parent en indexation depuis zéro et depuis un
Un tas binaire disposé dans un tableau ne stocke jamais de pointeurs vers le parent ni vers les enfants. La remontée d'un nœud vers son parent est une formule d'indice en forme fermée, et cette formule dépend de la numérotation du tableau depuis zéro ou depuis un.
Dans la convention à partir de zéro utilisée par C, Java, JavaScript, Python et la plupart des tas de production, la racine occupe l'indice zéro, les enfants du nœud i siègent à deux i plus un et deux i plus deux, et le parent d'un nœud non racine est le plancher de i moins un divisé par deux.
Dans la convention à partir de un utilisée par beaucoup de manuels, le pseudocode à la CLRS et certains gabarits de concours, la racine occupe l'indice un, les enfants siègent à deux i et deux i plus un, et le parent est simplement le plancher de i divisé par deux. Les deux identités sont exactes pour des indices entiers ; ce ne sont ni des approximations ni des formules interchangeables.
Ce calculateur applique l'identité correspondante après que vous avez choisi la convention, et refuse la racine parce que la racine n'a pas de parent. Confondre les deux conventions est l'erreur classique d'un : traiter un tableau de langage comme s'il partait de un, ou un schéma de manuel comme s'il partait de zéro, produit un parent à une case de la vérité et casse en silence le sift-up ainsi que le decrease-key.
Contrat d'entrée, forme de la réponse et erreurs
Lorsque indexing vaut zero, l'indice doit être au moins zéro ; lorsque indexing vaut one, l'indice doit être au moins un. La racine de la convention choisie — zéro dans un tas à partir de zéro, un dans un tas à partir de un — est refusée avec un message qui nomme cette racine, car inventer un parent en moins un ou boucler jusqu'à la dernière case serait un mensonge.
Exemple : indice cinq avec la convention à partir de zéro par défaut donne parent deux, car le plancher de quatre sur deux vaut deux. Exemple : indice quatre avec indexation à partir de un donne parent deux, alors que le même quatre dans un tas à partir de zéro aurait parent un — ce couple est toute la raison d'être du champ de convention. Une validation échouée n'est pas facturée.
Où un calculateur d'indice parent trouve son utilité
La préparation aux entretiens, les cours d'algorithmes et les files de priorité de production ont besoin de la même remontée vers le parent, et divergent sur la numérotation. Les étudiants qui vérifient une trace de sift-up veulent confirmer que le parent de cinq est deux dans un tableau de langage et que le parent de quatre est deux sur une feuille à partir de un, sans inverser la formule à la main à chaque pas.
Les correcteurs automatiques de devoirs de structures ont besoin d'un oracle déterministe qui refuse la racine faute de parent, au lieu de renvoyer un moins un silencieux qu'une copie fautive pourrait traiter comme un succès. Les ingénieurs qui portent un tas de manuel vers un langage à partir de zéro, ou l'inverse, peuvent figer les deux conventions dans les tests et attraper le décalage d'un avant la mise en production.
Les visualiseurs et échafaudages de concours qui dessinent l'arbre depuis un tableau peuvent demander le parent de chaque case non racine et tracer les arêtes sans embarquer deux copies de la formule. Gardez les requêtes modestes, figez l'entier parent dans les tests, et vous obtenez des remontées reproductibles pour devoirs, greffons LMS et workers en bordure sans dresser une bibliothèque locale de tas.
Cas d’usage
Traces de devoirs et d'entretiens
Vérifiez le parent de n'importe quelle case du tableau en suivant un sift-up ou un heapsort, en passant de la numérotation de manuel à partir de un aux tableaux de langage à partir de zéro.
Correcteurs automatiques et oracles de concours
Notez les questions d'indices de tas avec une formule déterministe du parent qui refuse la racine faute de parent, au lieu d'inventer un indice fictif.
Porter des tas d'une convention à l'autre
Figez les remontées vers le parent en traduisant un pseudocode CLRS à partir de un vers un tableau de langage à partir de zéro, ou l'inverse, avant que le décalage d'un ne parte en production.
Questions fréquentes
Comment obtenir le parent d'un nœud dans un tableau de tas binaire ?
Pour un tas à partir de zéro, le parent est floor((index − 1) / 2). Pour un tas à partir de un, le parent est floor(index / 2).
Quelle est la différence entre l'indexation depuis zéro et depuis un dans un tas ?
Un tas à partir de zéro place la racine à l'indice 0 et utilise parent = floor((i − 1) / 2). Un tas à partir de un place la racine à l'indice 1 et utilise parent = floor(i / 2). Le même nombre peut désigner des parents distincts selon la convention.
Que se passe-t-il si l'on demande le parent de la racine ?
La racine (indice 0 si indexing vaut zero, indice 1 si indexing vaut one) n'a pas de parent, et le calculateur n'en inventera pas.
Quel est le parent de l'indice 5 dans un tas binaire indexé à partir de zéro ?
Deux. floor((5 − 1) / 2) = 2. Le même indice dans un tas à partir de un vaut aussi 2, mais le 4 est le couple qui diverge : parent 1 à partir de zéro, parent 2 à partir de un.
Pourquoi une erreur d'un rang dans la formule du parent compte-t-elle autant ?
Parce que le résultat désigne une vraie case voisine du bon parent : rien ne plante, mais la remontée d'un élément et la baisse de priorité comparent et échangent les mauvais éléments, et l'ordre du tas se brise en silence.
Outils associés
Pour les développeurs — accès API
Tout sur cette page est disponible par programmation. Cette section s'adresse aux équipes qui veulent l'intégrer à leurs systèmes ; les autres peuvent simplement utiliser l'outil ci-dessus.
Endpoint
Authentification par jeton Bearer : un seul POST met la tâche en file d’attente, et le résultat vous parvient par webhook ou lien signé.
Appeler depuis votre stack
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)Exemple de requête
{
"index": 5
}Exemple de réponse
{
"task_id": "tsk_a1b2c3d4e5f6a1b2c3d4e5f6",
"type": "dev.heap_parent_index",
"status": "queued",
"_links": {
"result": "/tasks/tsk_…/result"
}
}L’API est asynchrone : chaque appel renvoie un task_id immédiatement, puis vous interrogez l’état à raison d’une requête par seconde.
Tarifs
Le prix est publié, sans tokens ni crédits. Une tâche qui échoue n’est pas facturée.
Erreurs
| HTTP | Code | Signification |
|---|---|---|
401 | unauthorized | Clé API absente ou invalide : vérifiez l’en-tête Authorization. |
402 | insufficient_balance | Solde insuffisant : rechargez votre compte pour lancer cette tâche. |
404 | unknown_type | Type de tâche inconnu : vérifiez le champ type de votre requête. |
429 | rate_limited | Trop de requêtes : ralentissez la cadence, puis réessayez. |
Notes techniques
Formules du parent en indexation depuis zéro et depuis un
La réponse répète l'indice et la convention que vous avez envoyés, nomme le parent, nomme l'indice racine de cette convention, reformule la formule en chaîne que vous pouvez imprimer à côté de la réponse, et place is_root à false à chaque remontée réussie afin que les clients traitent le succès comme « un parent réel existe ».
Contrat d'entrée, forme de la réponse et erreurs
Envoyez par POST un corps JSON avec index obligatoire : un entier fini qui nomme la case du tableau du nœud dont vous voulez le parent. indexing est facultatif et vaut zero par défaut, c'est-à-dire un tableau à partir de zéro dont la racine est à l'indice zéro ; envoyez one lorsque votre tas est numéroté à partir de un. Les alias i et node sont acceptés pour index, et convention pour indexing, afin que les extraits copiés de notes de cours s'analysent encore. Valeurs non finies, booléens, chaînes vides et index manquant échouent avec invalid_input. Les indices au-delà de la limite d'entier sûr sont refusés afin que les nombres JSON restent exacts sous la division plancher. En cas de succès le corps reprend l'index et l'indexing, parent comme entier calculé, is_root à false, root comme case racine de la convention, et formula comme parent égal au plancher de parenthèse indice moins un fermante sur deux, ou parent égal au plancher de l'indice sur deux.
Où un calculateur d'indice parent trouve son utilité
Comme il s'agit de parse de niveau A, chaque appel réussi coûte le tarif de base publié $0.002 sans jetons de modèle ni réseau sortant, et une entrée invalide ne consomme pas le solde.
Questions techniques
Combien coûte le calculateur d'indice parent d'un tas binaire ?
L'outil du navigateur est gratuit. Les requêtes API utilisent le solde prépayé KIT à $0.002 par appel réussi ; une entrée invalide n'est pas facturée.