Hasta donde yo sé, no existe ninguna ley que prohíba usar un montón para ordenar una lista enlazada, pero considere esto:

• Con el mismo enfoque, puede usar cualquier algoritmo de clasificación que se use en matrices: copie los valores de la lista en una matriz; ordene la matriz con su algoritmo favorito y vuelva a crear una lista vinculada a partir de la matriz.

• La mayoría de los desafíos de código que conciernen a las listas vinculadas esperarán que no use ninguna otra estructura de datos O(n), sino que se limite únicamente a las listas vinculadas. Dependiendo del desafío, incluso podría haber un requisito para usar solo la memoria auxiliar O(1).

• Si la memoria auxiliar O(1) es un requisito, entonces no es práctico convertir la lista enlazada en una organizada en montón: no puede ofrecer un recorrido eficiente de un nodo a su montón-hijo ni a su montón-padre. Por otro lado, se pueden implementar otros algoritmos eficientes como la ordenación por combinación y algún tipo de ordenación rápida utilizando una estructura de lista enlazada.

Sé cómo ordenar una lista enlazada usando la ordenación por combinación. La pregunta es, ¿por qué no usamos un montón para crear una LinkedList ordenada?

• Recorra la lista vinculada y siga agregando elementos a un montón mínimo.
• Siga sacando los elementos del montón y apile el montón y agréguelo a un nuevo resultado LinkedList.

Varias razones, entre ellas:

• La complejidad asintótica no es el final de la historia. La ordenación por combinación es especialmente limpia y eficiente de implementar para listas enlazadas, por lo que se encuentra entre las ordenaciones de lista enlazada O(n log n) con mejor rendimiento.

• Pero la complejidad asintótica sigue siendo parte de la historia. El tipo de montón de una matriz se puede hacer con el espacio auxiliar O (1) mediante el uso de relaciones entre los índices de la matriz para proporcionar una representación implícita del árbol. Esto admite la clasificación en pasos O (n log n) en general porque el acceso a una matriz por índice es O (1), pero no ocurre lo mismo con una lista vinculada. Para obtener un montón O(n log n) como una lista enlazada, debe construir el montón como un árbol real o como una matriz, lo que requiere una sobrecarga de O(n). Y luego es un poco forzado llamarlo tipo de lista enlazada, porque podría haber hecho exactamente lo mismo con una matriz o muchas otras estructuras de datos.

• Además, la ordenación por combinación se puede estabilizar fácilmente, pero eso es más difícil para la ordenación en montón y probablemente requiera una sobrecarga adicional.

Entonces, la clasificación se puede hacer en O (nlogn) si mi comprensión es correcta.

Claro, cualquier conjunto de datos que se pueda enumerar en pasos O (n) se puede cargar en una matriz y ordenar a través de cualquier algoritmo de clasificación de matriz O (n log n) aplicable en pasos O (n log n). En el caso particular de una lista enlazada, también se pueden reformar los nodos en una lista ordenada sin aumentar la complejidad asintótica.

Esto es lo mismo que el ordenamiento por fusión.

La misma complejidad asintótica no significa el mismo rendimiento. Una gran diferencia en el factor constante aún puede marcar una diferencia importante. Además, incluso si todo lo demás fuera igual, el código mucho más simple de clasificación de combinación de lista vinculada frente a lo que usted describe es una enorme ventaja de ingeniería. Significa un desarrollo más rápido y menos errores.

En términos de memoria, estamos usando un montón adicional, por lo que la memoria total puede ser O (nlogn), supongo. La ordenación por combinación también puede tomar O(nlogn) pero se puede mejorar a O(logn).

No tengo idea de dónde proviene su idea O (n log n) para ninguno de los casos. Cuento O (n) sobrecarga para una matriz auxiliar en el caso de clasificación de montón. En las matrices, las implementaciones típicas de clasificación por fusión tienen una sobrecarga O(n), pero en las listas vinculadas, la sobrecarga por O(log n) es natural para la clasificación por fusión.

Con respecto a este comentario:

En un libro, vi que no podremos ordenar una lista enlazada individualmente con ordenación rápida u ordenación en montón.

Ese libro estaba equivocado, incluso si no permitimos leer la lista enlazada en una matriz auxiliar u otra estructura de datos sobre la cual realizar la clasificación real. Si no permite una estructura auxiliar de este tipo, entonces no creo que pueda ordenar en montón en una lista de enlaces únicos en menos de o (n ² log n) pasos, pero puede hacerlo. Y no necesita un acceso aleatorio rápido o un recorrido bidireccional para realizar una ordenación rápida O (n log n).

Empujar elementos al montón y sacarlos son operaciones logarítmicas. Eliminar un elemento del montón es logarítmico porque el montón necesita ajustar sus elementos para garantizar que el montón sea invariable. Por lo tanto, haría 2 * n * log n , y si bien esto sigue siendo lineal rítmico en términos de Big O como merge sort, probablemente sea más lento. O digamos al menos que puede hacerlo mejor usando un algoritmo de ordenamiento lineal rítmico, en lugar de usar un montón para ordenar.

Lo que podría hacer, y no vi que lo mencionara, es agregar todos los elementos de la lista vinculada al almacén de datos del montón en tiempo O(n) y luego acumularlo, que también se ejecuta en O(n) si implementado correctamente. Entonces tendrías 2n + n * log n que se reduce a O(n * log n) con mejores constantes.

El espacio adicional utilizado por el montón no es O(n log n) . Es lineal y aunque esto depende de la implementación del montón, digamos que muchas implementaciones estándar del montón proporcionan eso.

Al fusionar k listas vinculadas ordenadas con un montón, se beneficia del hecho de que k es mucho más pequeño que la longitud de las listas mismas. Esto conduce a un algoritmo O((n1 + n2 +...) * log k) donde n1, n2,... son las longitudes de las listas involucradas. Si no usó un montón, ese algoritmo se habría ejecutado en O((n1 + n2 +...) * k) tiempo.

Al final del día, si un montón se implementa y usa correctamente, tendrá una complejidad de tiempo lineal rítmica y una complejidad de espacio lineal para ordenar la lista vinculada. Pero hagas lo que hagas, todas las demás variables son iguales, un algoritmo de clasificación estándar tiene mejores constantes que un montón cuando se trata de clasificar, a menos que existan algunos requisitos y restricciones especiales. Permítanme reiterar que ambos métodos son lineales en términos de Big O, pero los algoritmos de clasificación pueden tener mejores constantes para este propósito específico, lo que puede significar mucho en las aplicaciones del mundo real. La razón es que un montón necesita garantizar el acceso en tiempo O(1) al elemento más pequeño/más grande en cualquier momento. Esto impone restricciones en su comportamiento y no podría optimizarlo tanto como un algoritmo de clasificación estándar cuando se trata de clasificar.