Saltar al contenido
wandres.dev
Iniciar sesión

Simulación

Bajar

Para extraer el mínimo:

  1. Guardar la raíz para devolverla.
  2. Mover el último elemento a la raíz y acortar el array.
  3. Bajar: mientras sea mayor que alguno de sus hijos, intercambiarlo con el menor de ellos.

Primero mira un ejemplo con otro heap, [1, 4, 2, 6, 5, 3, 7], del que se extrae el 1:

Bajar la raíz, paso 1 de 4Array 7, 4, 2, 6, 5, 3 tras mover el último elemento a la raíz. El 7, raíz, y sus dos hijos, 4 y 2, tienen borde grueso.742653704122635435
Paso 1 de 4. Se guarda el 1 para devolverlo; el último elemento, 7, pasa a la raíz y el array se acorta. Los hijos de 7 son 4 y 2: el menor es 2.
Bajar la raíz, paso 2 de 4Array 2, 4, 7, 6, 5, 3. Las posiciones 0 (valor 2) y 2 (valor 7) están marcadas como cambiadas.2*47*6532*0417*2635435
Paso 2 de 4. 7 se intercambia con 2, el menor de sus hijos, no con 4.
Bajar la raíz, paso 3 de 4El mismo array 2, 4, 7, 6, 5, 3. El 7, en la posición 2, y su único hijo, 3, en la posición 5, tienen borde grueso. La posición 6 ya no existe.247653204172635435
Paso 3 de 4. 7 tiene un solo hijo, 3 (la posición 6 ya no existe). 3 es menor que 7: se intercambian.
Bajar la raíz, paso 4 de 4Array final 2, 4, 3, 6, 5, 7. Las posiciones 2 (valor 3) y 5 (valor 7) están marcadas como cambiadas.243*657*20413*263547*5
Paso 4 de 4. 7 es ahora una hoja: no tiene hijos con quien compararse y bajar termina. El array es un heap y se devolvió el 1.

Borde grueso: lo que se compara. Relleno con asterisco: lo que acaba de cambiar.

Ahora tú: extraes el mínimo de [1, 5, 2, 9, 7, 8, 3].

¿Qué secuencia de estados sigue el array al extraer el 1 de [1, 5, 2, 9, 7, 8, 3]?