complejidad Tiempo para obtener los elementos de max-min montón

Question

me preguntaron en una entrevista:

¿Cuál es la mejor complejidad del tiempo en conseguir el elemento (s) min desde un máximo en heap?

Respondí como O (1) suponiendo que se conoce el tamaño del montón y el montón se implementa como un montón binario utilizando una matriz. De esta manera, según mi suposición, el valor mínimo está en heap_array[heap_size].

Mi pregunta es que si esta respuesta es correcta. Si no, ¿cuál es la respuesta correcta?

Answer 1

Mi pregunta es que si la respuesta es correcta.

No, eso no es correcto. La única garantía que tiene es que cada nodo contiene el elemento máximo del subárbol debajo de él. En otras palabras, el elemento mínimo puede ser cualquier hoja en el árbol.

¿Cuál es la respuesta correcta?

La respuesta correcta es O (n). En cada paso, debe atravesar subárboles izquierdo y derecho para buscar el elemento mínimo. En efecto, esto significa que debe atravesar todos los elementos para encontrar el mínimo.

Answer 2

La mejor complejidad es O(n). Prueba de boceto:

• El elemento mínimo podría ser absolutamente cualquiera de los nodos de nivel más bajo (de hecho, incluso podría no estar en el nivel más bajo, pero comencemos con estos).
• Puede haber hasta n/2 nodos de nivel más bajo.
• Todos ellos deben ser examinados, porque el que está buscando podría estar en el último lugar que usted mira. Examinar todos-pero-1 de ellos no le dice si el último es el mínimo o no.
• Por lo tanto, Omega(n) exámenes requeridos.

El límite es estricto, ya que claramente podemos hacerlo en O(n) ignorando el hecho de que nuestra matriz es un montón.

Moral: probablemente se lo llame montón porque (como sucede con el montón de ropa en el piso de su habitación) es fácil llegar a la cima y es difícil llegar al descanso.

Answer 3

elemento Min Max montón:

1. búsqueda en último nivel = O (n/2) = O (n)

2. cambie el elemento buscado con último elemento y reducir el tamaño del montón por 1 = O (1)

3. Aplicar Maxheapify en elemento reemplazado = O (log n)

Tiempo total = O (n) + O (1) + O (log n) = O (n)

Answer 4

MINIMUM_ELEMENT -> tomará O (n) de tiempo en caso de Max montón y O (1) en el caso de Min heap. MAXIMUM_ELEMENT -> tardará O (1) vez en el caso de Max heap y O (n) en el caso de Min heap.