Ordenar montones en Python

Heap Sort es uno de los pocos algoritmos de clasificación eficientes de uso generalizado. Con un tiempo de ejecución constante de O(n*logn) y confiando en la estructura de datos del montón, Heap Sort ha encontrado su camino en muchos proyectos.

Introducción

Heap Sort es otro ejemplo de un algoritmo de clasificación eficiente. Su principal ventaja es que tiene un gran tiempo de ejecución en el peor de los casos de O(n*logn) independientemente de los datos de entrada.

Como sugiere el nombre, Heap Sort se basa en gran medida en la estructura de datos heap, una implementación común de una Cola de prioridad.

Sin duda, Heap Sort es uno de los algoritmos de clasificación más simples de implementar y, junto con el hecho de que es un algoritmo bastante eficiente en comparación con otras implementaciones simples, es común encontrarlo.

Clasificación en montón {#clasificación en montón}

Heap Sort funciona "eliminando" elementos de la parte del montón de la matriz uno por uno y agregándolos a la parte ordenada de la matriz. Antes de profundizar en la explicación y revisar la estructura de datos del montón, debemos mencionar algunos atributos de Heap Sort.

Es un algoritmo en el lugar, lo que significa que requiere una cantidad constante de memoria adicional, es decir, la memoria necesaria no depende del tamaño de la matriz inicial en sí, sino de la memoria necesaria para almacenar esa matriz.

Por ejemplo, no se necesitan copias de la matriz original y no hay recursividad ni pilas de llamadas recursivas. La implementación más simple de Heap Sort generalmente usa una segunda matriz para almacenar los valores ordenados. Usaremos este enfoque ya que es mucho más intuitivo y fácil de seguir en el código, pero se puede implementar completamente in situ.

Heap Sort es inestable, lo que significa que no mantiene el orden relativo de los elementos con valores iguales. Esto no es un problema con tipos primitivos (como enteros y caracteres...) pero puede ser un problema cuando ordenamos tipos complejos, como objetos.

Por ejemplo, imagine que tenemos una clase personalizada Persona con los campos edad y nombre, y varios objetos de esa clase en una matriz, incluida una persona llamada "Mike" de 19 años y "David" , también de 19 años - apareciendo en ese orden.

Si decidiéramos clasificar esa matriz de personas por edad, no habría garantía de que "Mike" apareciera antes que "David" en la matriz ordenada, aunque aparecieran en ese orden en la matriz inicial. Puede suceder, pero no está garantizado.

Dato curioso: Heap Sort es el algoritmo de clasificación elegido en el Núcleo de Linux

La estructura de datos del montón

Los montones son una de las estructuras de datos más populares y más utilizadas en informática, sin mencionar que son muy populares durante las entrevistas de ingeniería de software.

Hablaremos de montones que realizan un seguimiento del elemento más pequeño (min-heap), pero pueden implementarse con la misma facilidad para realizar un seguimiento del elemento más grande (max-heap).

En pocas palabras, un montón mínimo es una estructura de datos basada en árboles en la que cada nodo es más pequeño que todos sus elementos secundarios. La mayoría de las veces se usa un árbol binario. Los montones tienen tres operaciones admitidas: delete_minimum(), get_minimum() y add().

Puede solo eliminar el primer elemento del montón, después de lo cual se "reordena". Los montones se "reordenan" después de agregar o eliminar un elemento, de modo que el elemento más pequeño esté siempre en la primera posición.

Nota: Esto de ninguna manera significa que los montones son matrices ordenadas. El hecho de que cada nodo sea más pequeño que sus hijos no es suficiente para garantizar que todo el montón esté en orden ascendente.

Veamos un ejemplo de un montón:

Como podemos ver, el ejemplo anterior se ajusta a la descripción de un montón, pero no está ordenado. No entraremos en detalles de la implementación del montón ya que ese no es el enfoque de este artículo. La ventaja crucial de la estructura de datos del montón que aprovechamos cuando la usamos en Heap Sort es que el siguiente elemento más pequeño es siempre el primer elemento del montón.

Nota: Gracias a la forma en que los montones ordenan los elementos después de que se elimina un elemento, la complejidad del siguiente elemento más pequeño que se mueve a la primera posición, mientras se mantiene el arreglo en un montón, toma O(logn) tiempo, que es una operación altamente eficiente.

Implementación

Clasificación de matrices {#clasificación de matrices}

Python proporciona métodos para crear y usar montones para que no tengamos que implementarlos nosotros mismos:

  • heappush(list, item): agrega un elemento al montón y luego lo reordena para que siga siendo un montón. Se puede utilizar en una lista vacía.
  • heappop(list): extrae (elimina) el primer elemento (el más pequeño) y lo devuelve. El montón sigue siendo un montón después de esta operación, por lo que no tenemos que llamar a heapify().
  • heapify(list): Convierte la lista dada en un montón. Vale la pena señalar que este método existe aunque no lo usaremos ya que no queremos cambiar nuestra matriz original.

Ahora que sabemos esto, la implementación de Heap Sort es bastante sencilla:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
from heapq import heappop, heappush

def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)

    ordered = []

    # While we have elements left in the heap
    while heap:
        ordered.append(heappop(heap))

    return ordered

array = [13, 21, 15, 5, 26, 4, 17, 18, 24, 2]
print(heap_sort(array))

Producción:

1
[2, 4, 5, 13, 15, 17, 18, 21, 24, 26]

Como podemos ver, el trabajo pesado se hace con la estructura de datos del montón, todo lo que tenemos que hacer es agregar todos los elementos que necesitamos y eliminarlos uno por uno. Es casi como una máquina contadora de monedas que clasifica las monedas ingresadas por su valor y podemos sacarlas después.

Clasificación de objetos personalizados

Las cosas se complican un poco más cuando se usan clases personalizadas. Por lo general, desaconsejamos anular los operadores de comparación en las clases con el fin de usar nuestros algoritmos de clasificación para ellos y, en su lugar, sugerimos reescribir el algoritmo para que tome un comparador de función lambda.

Sin embargo, dado que nuestra implementación se basa en los métodos de montón incorporados, no podemos hacer eso aquí.

Python proporciona los siguientes métodos:

  • heapq.nlargest(*n*, *iterable*, *key=None*): Devuelve una lista con los n elementos más grandes del conjunto de datos definido por iterable.
  • heapq.nsmallest(*n*, *iterable*, *key=None*): Devuelve una lista con los n elementos más pequeños del conjunto de datos definido por iterable.

Que podríamos usar simplemente para obtener n = len(array) elementos más grandes/más pequeños, pero los métodos en sí mismos no usan Heap Sort y son esencialmente equivalentes a simplemente llamar al método sorted().

La única solución que nos queda para las clases personalizadas es anular los operadores de comparación. Lamentablemente, esto nos limita a un solo tipo de comparación por clase. En nuestro ejemplo, nos limita a clasificar los objetos Película por año.

Sin embargo, nos permite demostrar el uso de Heap Sort en clases personalizadas. Avancemos y definamos la clase Película:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
from heapq import heappop, heappush

class Movie:
    def __init__(self, title, year):
        self.title = title
        self.year = year

    def __str__(self):
        return str.format("Title: {}, Year: {}", self.title, self.year)

    def __lt__(self, other):
        return self.year < other.year

    def __gt__(self, other):
        return other.__lt__(self)

    def __eq__(self, other):
        return self.year == other.year

    def __ne__(self, other):
        return not self.__eq__(other)

Y ahora, modifiquemos ligeramente nuestra función heap_sort():

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
def heap_sort(array):
    heap = []
    for element in array:
        heappush(heap, element)

    ordered = []

    while heap:
        ordered.append(heappop(heap))

    return ordered

Y finalmente, vamos a crear una instancia de algunas películas, ponerlas en una matriz y luego ordenarlas:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
movie1 = Movie("Citizen Kane", 1941)
movie2 = Movie("Back to the Future", 1985)
movie3 = Movie("Forrest Gump", 1994)
movie4 = Movie("The Silence of the Lambs", 1991);
movie5 = Movie("Gia", 1998)

array = [movie1, movie2, movie3, movie4, movie5]

for movie in heap_sort(array):
    print(movie)

Producción:

1
2
3
4
5
Title: Citizen Kane, Year: 1941
Title: Back to the Future, Year: 1985
Title: The Silence of the Lambs, Year: 1991
Title: Forrest Gump, Year: 1994
Title: Gia, Year: 1998

Comparación con otros algoritmos de clasificación {#comparación con otros algoritmos de clasificación}

Una de las principales razones por las que Heap Sort todavía se usa con bastante frecuencia, aunque a menudo es superado por una Ordenación rápida bien implementada, es su confiabilidad.

La principal ventaja de Heap Sort aquí es el límite superior O(n*logn) en lo que respecta a la complejidad del tiempo y las preocupaciones de seguridad. Los desarrolladores del kernel de Linux dan el siguiente razonamiento para usar Heap Sort sobre Quick Sort:

El tiempo de clasificación de Heap Sort es O(n*logn) tanto en promedio como en el peor de los casos. Si bien qsort es aproximadamente un 20 % más rápido en promedio, adolece de un comportamiento en el peor de los casos explotable O(n*n) y requisitos de memoria adicionales que lo hacen menos adecuado para el uso del kernel.

Además, Quick Sort se comporta mal en situaciones predecibles y, dado el conocimiento suficiente de la implementación interna, podría crear un riesgo de seguridad (principalmente ataques DDoS) ya que el mal comportamiento O(n^2^) podría desencadenarse fácilmente.

Another algorithm that Heap Sort is often compared to is Ordenar por fusión, which has the same time complexity.

Merge Sort tiene la ventaja de ser estable e intuitivamente paralelizable, mientras que Heap Sort no lo es.

Otra nota es que Heap Sort es más lento que Merge Sort en la mayoría de los casos, aunque tienen la misma complejidad, ya que Heap Sort tiene factores constantes más grandes.

Sin embargo, Heap Sort puede implementarse mucho más fácilmente in situ que Merge Sort, por lo que es preferible cuando la memoria es un factor más importante que la velocidad.

Conclusión

Como vimos, Heap Sort no es tan popular como otros algoritmos eficientes de propósito general, pero su comportamiento predecible (aparte de ser inestable) lo convierte en un gran algoritmo para usar cuando la memoria y la seguridad son más importantes que un tiempo de ejecución ligeramente más rápido. .

Es realmente intuitivo de implementar y aprovechar la funcionalidad integrada provista con Python, todo lo que tenemos que hacer esencialmente es poner los elementos en un montón y sacarlos, similar a un contador de monedas. .