Un problème de tas d-aire de CLRS

10

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.

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

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

  3. 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 .

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

  5. 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

  1. Donnez un tableauA[a1..an]

    root:a1level 1:a2a2+d1level 2:a2+da2+d+d21level k:a2+i=1k1dia2+i=1kdi1

    Ma notation semble un peu sophistiquée. Y en a-t-il un autre plus simple?

  2. Soit h la hauteur du tas d -aire.

    Supposons que le tas soit un arbre d -ary complet

    1+d+d2+..+dh=ndh+11d1=nh=logd[nd1+1]1
  3. 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:

      TM=d(c8d+(c9+..+c13)d+c14d)
      où désigne le coût de la i- ème ligne ci-dessus.ci
    • EXTRACT-MAX:

      TE=(c1+..+c7)+TMCdh=Cd(logd[n(d1)+1]1)=O(dlogd[n(d1)])

    Est-ce une solution efficace? Ou il y a quelque chose qui ne va pas dans ma solution?

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:

10
  1. 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.

    d-ary-parent(i)    return (i2)/d+1

    d-ary-child(i,j)    return d(i1)+j+1

    Évidemment . Vous pouvez vérifier ces fonctions en vérifiant que1jdd-ary-parent(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.dd=2d2

  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=logd(nd1+1)1logd(nd)1=logd(n)+logd(d)1=logd(n)+11=logd(n)Θ(logd(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Θ

  3. 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.AUXd-ary-parentd-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:EXTRACT-MAXMAX-HEAPIFYO(d logd(n(d1)))

    O(d logd(n(d1)))=O(d(logd(n)+log(d1)))=O(d logd(n)+d logd(d1))

    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 .dndlogd(d1)O(dlogd(n))MAX-HEAPIFYOΘ

  4. Le livre CLRS fournit déjà la procédure INSERT. Qui ressemble à ceci:

    INSERT(A,key)    A.heap_size=A.heap_size+1    A[A.heap_size]=    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(logd(n))

  5. Tout comme INSERT, INCREASE-KEY est également défini dans le manuel comme:

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

    La complexité est évidemment (voir point précédent).O(logd(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
1

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=logd[nd1+1]1
h = Θ ( log d ( n ) )
1+d+d2+..+dh=ndh+11d1=nh=logd[n(d1)+1]1
h=Θ(logd(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
4
Pourquoi est-ce la réponse? Une formule sans explication n'aide vraiment personne.
David Richerby