PUERTA | GATE-CS-2016 (Conjunto 1) | Pregunta 47

Se debe diseñar un operador delete(i) para una estructura de datos de almacenamiento dinámico binario para eliminar el elemento en el i-ésimo Node. Suponga que el montón se implementa en una array y me refiero al i-ésimo índice de la array. Si el árbol del montón tiene una profundidad d (número de aristas en el camino desde la raíz hasta la hoja más lejana), ¿cuál es la complejidad del tiempo para volver a arreglar el montón de manera eficiente después de eliminar el elemento?
(A) O(1)
(B) O(d) pero no O(1)
(C) O(2 ^d ) pero no O(d)
(D) O(d2 ^d ) pero no O(2 ^d )

Respuesta: (B)
Explicación:  

Para esta pregunta, tenemos que modificar ligeramente la operación delete_min() de la estructura de datos del montón para implementar la operación delete( i ). La idea es vaciar el lugar en la array en el índice i (la posición en la que se eliminará el elemento) y reemplazarlo con la última hoja en el montón (recuerde que el montón se implementa como un árbol binario completo para que sepa la ubicación de la última hoja), disminuya el tamaño del montón y ahora comience desde la posición actual i(posición que contenía el elemento que eliminamos), muévalo hacia arriba en caso de que el elemento recién reemplazado sea mayor que el padre del elemento anterior (considerando el montón máximo). Si no es mayor que el padre, entonces filtre hacia abajo comparándolo con el valor del hijo. El elemento recién agregado puede filtrarse hacia arriba/abajo un máximo de d veces, que es la profundidad de la estructura de datos del montón.

Así podemos decir que la complejidad de delete( i ) sería O(d) pero no O(1).

http://geeksquiz.com/binary-heap/

Esta solución es aportada por Pranjul Ahuja .
Cuestionario de esta pregunta