tipo de montón 1-aria?

Question

Hace un tiempo nos dieron la tarea de escribir un programa c que ordena una matriz de n números usando un max-heap d-ary (un montón donde cada nodo tiene hasta d hijos). El programa necesitaba pedirle al usuario que ingrese el valor de d, un valor entre 2 y el tamaño de la matriz. Mientras estaba revisando mi programa, accidentalmente ingresé 1 como el valor de d, y de alguna manera el algoritmo logró clasificar la matriz correctamente usando un montón de 1 aria, aunque tardó mucho más tiempo que los valores normales de d.

¿Cómo es eso posible? Un montón de 1-aria ni siquiera es un montón, es como una lista, cada nodo tiene un solo hijo. ¿Alguien puede explicar cómo podría suceder esta clasificación?

Answer 1

Un montón 1-aria es todavía un montón, y satisface todos los invariantes que son requeridos por una pila de clasificación:

• El primer elemento es el elemento más grande.
• La percolación puede mover el elemento superior a su posición correcta.

En la práctica, un montón 1-ary es un árbol donde cada nodo tiene un elemento secundario, también conocido como lista individualmente vinculada. Además, la restricción de montón significa que el nodo hijo es más pequeño que el nodo padre. Entonces, en pocas palabras, un montón 1-ary es una lista unida individualmente ordenada en orden inverso.

Construir el montón en primer lugar es equivalente a una ordenación de inserción (filtrar todos los elementos en la lista uno por uno). Una vez hecho esto, eliminar el primer elemento produce el elemento más grande de todos, y la percolación posterior mueve cada elemento de la lista un nivel.