Un problème de tas d-aire de CLRS

Je suis devenu confus en résolvant le problème suivant (questions 1 à 3).

Question

Un tas d -ary est comme un tas binaire, mais (à une exception possible) les nœuds non-feuilles ont d enfants au lieu de 2 enfants.

Comment représenteriez-vous un tas d -ary dans un tableau?

Quelle est la hauteur d'un tas d -aire de n éléments en termes de n et d ?

Donner une implémentation efficace d'EXTRACT-MAX dans un tas max d -ary. Analysez son temps de fonctionnement en termes de d et n .

_{Donner une implémentation efficace de INSERT dans un tas max d -ary. Analysez son temps de fonctionnement en termes de d et n .}

_{Donnez une implémentation efficace de INCREASE-KEY ( A , i , k ), qui signale une erreur si k <A [i] = k, puis met à jour la structure de tas de la matrice d -ary de manière appropriée. Analysez son temps de fonctionnement en termes de d et n .}

Ma solution

Donnez un tableau $A[a_1 .. a_n]$

$\qquad \begin{align} \text{root} &: a_1\\ \text{level 1} &: a_{2} \dots a_{2+d-1}\\ \text{level 2} &: a_{2+d} \dots a_{2+d+d^2-1}\\ &\vdots\\ \text{level k} &: a_{2+\sum\limits_{i=1}^{k-1}d^i} \dots a_{2+\sum\limits_{i=1}^{k}d^i-1} \end{align}$

→ Ma notation semble un peu sophistiquée. Y en a-t-il un autre plus simple?
Soit h la hauteur du tas d -aire.

Supposons que le tas soit un arbre d -ary complet
$1 + d + d^{2} + . . + d^{h} = n \frac{d^{h + 1} - 1}{d - 1} = n h = l o g_{d} [n d - 1 + 1] - 1$ $1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n{d-1}+1] - 1$
Voici ma mise en œuvre:
```
EXTRACT-MAX(A)
1  if A.heapsize < 1
2      error "heap underflow"
3  max = A[1]
4  A[1] = A[A.heapsize]
5  A.heap-size = A.heap-size - 1
6  MAX-HEAPIFY(A, 1)
7  return max

MAX-HEAPIFY(A, i)
1  assign depthk-children to AUX[1..d]
2  for k=1 to d
3      compare A[i] with AUX[k]
4      if A[i] <= AUX[k]
5          exchange A[i] with AUX[k]
6          k = largest
7  assign AUX[1..d] back to A[depthk-children]
8  if largest != i
9      MAX-HEAPIFY(A, (2+(1+d+d^2+..+d^{k-1})+(largest-1) )
```
- La durée de fonctionnement de MAX-HEAPIFY:
  
  $T_{M} = d (c_{8} * d + (c_{9} + . . + c_{1} 3) * d + c_{1} 4 * d)$ $T_M = d(c_8*d + (c_9+..+c_13)*d +c_14*d)$ où désigne le coût de la i- ème ligne ci-dessus. $c_i$
- EXTRACT-MAX:
  $T_{E} = (c_{1} + . . + c_{7}) + T_{M} \leq C * d * h = C * d * (l o g_{d} [n (d - 1) + 1] - 1) = O (d l o g_{d} [n (d - 1)])$ $T_E = (c_1+..+c_7) + T_M \leq C*d*h\\ = C*d*(log_d[n(d-1)+1] - 1)\\ = O(dlog_d[n(d-1)])$
→ Est-ce une solution efficace? Ou il y a quelque chose qui ne va pas dans ma solution?

data-structures time-complexity runtime-analysis lucasKo
la source

Je pense qu'il y a une légère erreur dans la question ainsi que l'explication: la hauteur du tas d-aire vient à h = (log [nd - n + 1]) - 1 // NOTE son "-n" et non "-1" et non h = (log [nd−1+1])− 1Ainsi, l'explication ci-dessus pour la hauteur ne sera pas vraie. h = log [nd − 1 + 1] −1 = log [nd] -1 = log [n] Bien que néanmoins, la hauteur de l'arbre soit écrite comme Θ(log(n)).Remarque: log est toujours à la base d pour un tas d-aire .

Surabhi Raje

Réponses:

Votre solution est valide et suit la définition du tas d -ary. Mais comme vous l'avez souligné, votre notation est un peu sophistiquée.

Vous pouvez utiliser les deux fonctions suivantes pour récupérer le parent du i- ème élément et le j- ème enfant du i- ème élément.

$\text{d-ary-parent}({\it i}) \\ \ \ \ \ {\bf return}\ \lfloor (i-2)/d + 1 \rfloor$

$\text{d-ary-child}(i, j) \\ \ \ \ \ {\bf return}\ d(i-1)+j+1$

Évidemment . Vous pouvez vérifier ces fonctions en vérifiant que $1 \le j \le d$ $\text{d-ary-parent}(\text{d-ary-child}(i,j)) = i$

Il est également facile de voir que le tas binaire est un type spécial de tas -ary où , si vous remplacez par , alors vous verrez qu'ils correspondent aux fonctions PARENT, LEFT et RIGHT mentionnées dans le livre. $d$ $d=2$ $d$ $2$
Si je comprends bien votre réponse, vous utilisez une progression géométrique . Dans votre cas, vous obtenez go , qui est évidemment , qui est en fait une solution valide et correcte. Mais juste pour gérer les fluctuations constantes, vous voudrez peut-être écrire . $h = log_d(n\,d-1+1) - 1$ $\log_d(n\,d) - 1 = \log_d(n) + \log_d(d) - 1 = \log_d(n) + 1 - 1 = \log_d(n)$ $\Theta(\log_d(n))$

La raison en est que certains tas peuvent ne pas être équilibrés, donc leur chemin le plus long et le chemin le plus court migrent varient selon une constante , en utilisant la notation , vous éliminez ce problème. $c$ $\Theta$
Vous n'avez pas besoin de réimplémenter la procédure donnée dans le manuel, mais vous devez la modifier un peu, par exemple en affectant tous les enfants à la table utilisant et les fonctions. $AUX$ $\text{d-ary-parent}$ $\text{d-ary-child}$

Étant donné que n'a pas été modifié, cela dépend du temps d'exécution de . Dans votre analyse, vous devez maintenant utiliser le pire des cas proportionnel à la taille et au nombre d'enfants que chaque nœud doit examiner (qui est au plus d ). Encore une fois votre analyse est très précise, vous avez finalement obtenu , qui peut être transformé en: $\text{EXTRACT-MAX}$ $\text{MAX-HEAPIFY}$ $O(d\ \log_d(n(d-1)))$

$O(d\ \log_d(n(d-1))) = O(d(\log_d(n) + \log(d-1))) = O(d\ log_d(n) + d\ \log_d(d-1))$

Pour des raisons pratiques, nous pouvons toujours supposer que , nous pouvons donc perdre la partie de la notation O , puis nous obtiendrons . Ce qui est également une solution valable. Mais sans surprise, vous pouvez également analyser le temps d'exécution des fonctions en utilisant le théorème maître , qui montrera que n'est pas seulement mais même . $d \ll n$ $d \log_d(d-1)$ $O(d\log_d(n))$ $\text{MAX-HEAPIFY}$ $O$ $\Theta$
Le livre CLRS fournit déjà la procédure INSERT. Qui ressemble à ceci:

$\text{INSERT}(A, key)\\ \ \ \ \ A.heap\_size = A.heap\_size + 1 \\ \ \ \ \ A[A.heap\_size] = -\infty\\ \ \ \ \ \text{INCREASE-KEY}(A, A.heap\_size, key)$

Cela peut être facile à prouver, mais le bon sens veut que sa complexité temporelle soit . C'est parce que le tas peut être traversé jusqu'à la racine. $O(\log_d(n))$
Tout comme INSERT, INCREASE-KEY est également défini dans le manuel comme:

$\text{INCREASE-KEY}(A, i, key)\\ \ \ \ \ {\bf if}\ key < A[i]\\ \ \ \ \ \ \ \ \ {\bf error} \text{"new key is smaller then current"}\\ \ \ \ \ A[i] = key\\ \ \ \ \ {\bf while}\ i > 1\ and\ A[i] > A[\text{d-ary-parent}(i)]\\ \ \ \ \ \ \ \ \ A[i] \leftrightarrow A[\text{d-ary-parent(i)}]\\ \ \ \ \ \ \ \ \ i = \text{d-ary-parent(i)}$

La complexité est évidemment (voir point précédent). $O(\log_d(n))$

Bartosz Przybylski
la source

Merci! Qu'en est-il de la mise en œuvre de INCREASE-KEY et INSERT? J'essaie de l'écrire, mais il a donné un appel récursif deux fois de MAX-HEAPIFY. Y a-t-il une meilleure solution? J'ai trouvé peu d'informations sur le web et le wiki

lucasKo

C'est du reste de l'exercice? Si oui, veuillez mettre à jour votre question et je serai heureux de répondre au thème.

Bartosz Przybylski

J'ai mis cette question sur le post édité.

lucasKo

réimplémenter la procédure INSERT? Vous voulez dire, il n'a pas besoin d'appeler la procédure qui ajuste l'ordre dans le tas, après avoir inséré un nouvel élément? Je ne comprends pas ...

lucasKo

Cette description était un peu malheureuse, voir les modifications pour la clearification.

Bartosz Przybylski

Ce n'est pas une réponse complète. partie b) la solution n'est pas Son comme l'a souligné l'utilisateur 55463 (parce qu'il ne peut pas commenter, mais répondre), mais a voté en raison du manque d'explication . La réponse votée l'a également résolu par erreur. La réponse sera toujours Source: problème 2-2. Analyse des tas d -ary, partie b)

h = l o g_{d} [n d - 1 + 1] - 1

$h=log_d[n{d-1}+1] - 1$

1 + d + d^{2} + . . + d^{h} = n \frac{d^{h + 1} - 1}{d - 1} = n h = l o g_{d} [n (d - 1) + 1] - 1

$1+d+d^2+..+d^h=n\\ \dfrac{d^{h+1}-1}{d-1}=n\\ h=log_d[n(d-1)+1] - 1$

h = Θ (\log_{d} (n))

$h=\Theta(\log_d(n))$

Ali Jazib Mahmood
la source

-1

La réponse à la deuxième question est h = log _d (n (d-1) + 1) - 1 Donc, h = log _d (nd - n + 1) - 1

user55463
la source

Pourquoi est-ce la réponse? Une formule sans explication n'aide vraiment personne.

David Richerby