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.
¿Cómo se representan una d montón ary en una matriz?
¿Cuál es la altura de un montón d -ary de n elementos en términos de n y d ?
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 .
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 .
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
Dar una matriz
→ Mi notación parece un poco sofisticada. ¿Hay alguna otra más simple?
Sea h denota la altura del montón d -ary.
Supongamos que el montón es un árbol completo d -ary
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:
→ ¿Es esta una solución eficiente? ¿O hay algo mal en mi solución?
h = (log [nd−1+1])− 1
Por 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 .Respuestas:
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 .
El libro CLRS ya proporciona el procedimiento INSERT. Que se ve así:
Al igual que INSERT, INCREASE-KEY también se define en el libro de texto como:
fuente
fuente
La respuesta a la segunda pregunta es h = log d (n (d-1) + 1) - 1 Entonces, h = log d (nd - n + 1) - 1
fuente