Advertencia: no has iniciado sesión. Tu dirección IP se hará pública si haces cualquier edición. Si
inicias sesión o
creas una cuenta, tus ediciones se atribuirán a tu nombre de usuario, además de otros beneficios.
Puedes deshacer la edición.
Antes de deshacer la edición, comprueba la siguiente comparación para verificar que realmente es lo que quieres hacer, y entonces publica los cambios para así efectuar la reversión.
Revisión actual |
Tu texto |
Línea 44: |
Línea 44: |
| * b) Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap. | | * b) Sean S[i] y S[j] claves del heap / i < j y S[i] > S[j] → el arreglo obtenido al intercambiar S[i] y S[j] sigue siendo max-heap. |
|
| |
|
| === Soluciones ===
| |
| a) <b>Falso</b>. Un contraejemplo sería el del heap representado por el arreglo [10, 3, 9, 2, 1, 8, 7]. Si tomamos i = 2 y j = 3, S[i] = 3 y S[j] = 9 => i < j y S[i] < S[j]. Si intercambiamos S[i] con S[j], los hijos del nodo con valor 3 pasarían a ser los antiguos hijos del nodo con valor 9, que eran los nodos con valores 8 y 7. Como 8 y 7 son mayores que su nuevo padre 3, el invariante del max-heap se pierde.
| |
|
| |
| b) <b>Falso</b>. El contraejemplo es muy parecido al anterior. Tomemos el heap representado por el arreglo [10, 9, 3, 8, 7]. Si tomamos i = 2 y j = 3, S[i] = 9 y S[j] = 3 => i < j y S[i] > S[j]. Si intercambiamos ahora los dos valores, el nodo con valor 3 pasará a ser el padre de los nodos con valores 8 y 7, y se romperá la invariante del max-heap.
| |
|
| |
|
| == Ejercicio 4 == | | == Ejercicio 4 == |