elementos de inserción en binario Montones Min

Question

Si Estoy insertando elementos: 10,12,14,1,6 min en un montón binario un artículo tras otro cómo serían los resultados parecerse, mi problema es el siguiente

cuando inicio tengo:

10 

continuación

10 
/
12 

continuación

10 
/\ 
12 14 

continuación

1 
/\ 
10 14 
/
12 

pero esto no está bien, así que ¿cuál es la forma correcta de hacer eso?

Nota: esta es una pregunta para la tarea, estoy tratando de entender el concepto, si no se siente cómodo resolviendo la pregunta (de todos modos, no es la pregunta completa) proporcione un ejemplo con un problema similar.

Answer 1

Tienes que agregar el nuevo elemento como un niño (o una hoja exactamente) al montón (no como raíz), eso significa que lo pones en el primer lugar libre "derecho" (o en tu montón de matriz, solo al final).

Luego tiene que restablecer las condiciones del montón, esto se llama "heapify". Esto sucede en dos fases:

1. intercambiar repetidamente el nuevo elemento (general: el elemento que viola las condiciones del montón) con su nodo padre con tal de que es más pequeño que el padre y no es la raíz.
2. Intercambie repetidamente el nuevo elemento con el elemento secundario con el valor más pequeño, hasta que el nuevo elemento se convierta en un permiso o ambos nodos hijos sean más grandes que el elemento en sí.

Eso significa

10 
/\ 
12 14 

+ 1 conduce a

10 
/\ 
12 14 
/
1 

Y que viole las condiciones del montón, así que hay que heapify

10 
/\ 
    1 14 
/
12 

Pero esto no es todavía bien, entonces tienes que heapificar nuevamente

 1 
/\ 
10 14 
/
12 

y ya está ... todo bien ahora :-)

Answer 2

step1:  10 
step2:  10 
     /
     12 
step3:  10 
     /\ 
     12 14 
step4:  1 
     /\ 
     10 12 
     /
     14 
step5:  1 
     /\ 
     6 10 
     /\ 
     12 14