Un problema de almacenamiento dinámico de CLRS

10

Me confundí al resolver el siguiente problema (preguntas 1–3).

Pregunta

Un montón d -ary es como un montón binario, pero (con una posible excepción) los nodos no hoja tienen d hijos en lugar de 2 hijos.

  1. ¿Cómo se representan una d montón ary en una matriz?

  2. ¿Cuál es la altura de un montón d -ary de n elementos en términos de n y d ?

  3. Dar una implementación eficiente de extracto-MAX en un d ary max-heap. Analice su tiempo de ejecución en términos de d y n .

  4. Proporcione una implementación eficiente de INSERT en un d -ary max-heap. Analice su tiempo de ejecución en términos de d y n .

  5. Dar una implementación eficiente de AUMENTO-KEY ( A , i , k ), que banderas un error si k <A [i] = k y luego actualiza el d ary matriz montón estructura apropiada. Analice su tiempo de ejecución en términos de d y n .

Mi solución

  1. Dar una matriz A[a1..an]

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

    Mi notación parece un poco sofisticada. ¿Hay alguna otra más simple?

  2. Sea h denota la altura del montón d -ary.

    Supongamos que el montón es un árbol completo d -ary

    1+d+d2+..+dh=ndh+11d1=nh=logd[nd1+1]1
  3. Esta es mi implementación:

    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) )
    
    • El tiempo de ejecución de MAX-HEAPIFY:

      TM=d(c8d+(c9+..+c13)d+c14d)
      ci
    • TE=(c1+..+c7)+TMCdh=Cd(logd[n(d1)+1]1)=O(dlogd[n(d1)])

    ¿Es esta una solución eficiente? ¿O hay algo mal en mi solución?

lucasKo
fuente
Creo que hay un pequeño error en la pregunta, así como en la explicación: la altura del montón d-ary llega a h = (log [nd - n + 1]) - 1 // NOTA su "-n" y no "-1" y no h = (log [nd−1+1])− 1Por lo tanto, la explicación anterior para la altura no será cierta. h = log [nd − 1 + 1] −1 = log [nd] -1 = log [n] Aunque, no obstante, la altura del árbol se escribe como Θ(log(n)).Nota: log siempre está en la base d para un montón d-ary .
Surabhi Raje

Respuestas:

10
  1. Su solución es válida y sigue definición de d montón ary. Pero como usted señaló, su notación es un poco sofisticada.

    Puede utilizar las dos funciones siguientes para recuperar el elemento primario del elemento i y el elemento secundario j del elemento i .

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

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

    1jdd-ary-parent(d-ary-child(i,j))=i

    dd=2d2

  2. h=logd(nd1+1)1logd(nd)1=logd(n)+logd(d)1=logd(n)+11=logd(n)Θ(logd(n))

    cΘ

  3. AUXd-ary-parentd-ary-child

    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))

    dndlogd(d1)O(dlogd(n))MAX-HEAPIFYOΘ

  4. El libro CLRS ya proporciona el procedimiento INSERT. Que se ve así:

    INSERT(A,key)    A.heap_size=A.heap_size+1    A[A.heap_size]=    INCREASE-KEY(A,A.heap_size,key)

    O(logd(n))

  5. Al igual que INSERT, INCREASE-KEY también se define en el libro de texto como:

    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)

    O(logd(n))

Bartosz Przybylski
fuente
¡Gracias! ¿Qué tal la implementación de INCREASE-KEY e INSERT? Intento escribirlo, pero dio dos veces recursiva llamada de MAX-HEAPIFY. ¿Hay una mejor solución? Encontré poca información en la web y wiki
lucasKo
¿Es eso descanso del ejercicio? Si es así, actualice su pregunta y me complacerá responder el tema.
Bartosz Przybylski
Puse esas preguntas en la publicación editada.
lucasKo
reimplementar el procedimiento INSERT? ¿Quiere decir que no tiene que llamar al procedimiento que ajusta el orden dentro del montón después de insertar un nuevo elemento? No lo entiendo ...
lucasKo
Esa descripción fue un poco desafortunada, ver ediciones para aclaración.
Bartosz Przybylski
1

h=logd[nd1+1]1
1+d+d2+..+dh=ndh+11d1=nh=logd[n(d1)+1]1
h=Θ(logd(n))
Ali Jazib Mahmood
fuente
-1

La respuesta a la segunda pregunta es h = log d (n (d-1) + 1) - 1 Entonces, h = log d (nd - n + 1) - 1

usuario55463
fuente
44
¿Por qué es esta la respuesta? Una fórmula sin explicación realmente no ayuda a nadie.
David Richerby