Ordenar mont贸n en Python

    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 del mont贸n, una implementaci贸n com煤n de una cola de prioridad.

    Sin lugar a dudas, 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.

    Ordenar 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 volver a visitar la estructura de datos del mont贸n, debemos mencionar algunos atributos del propio Heap Sort.

    Es un algoritmo in situ, 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铆, aparte 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 sencilla de Heap Sort suele utilizar 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 en el lugar.

    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 los tipos primitivos (como enteros y caracteres …) pero puede ser un problema cuando ordenamos tipos complejos, como objetos.

    Por ejemplo, imagina que tenemos una clase personalizada Person con el age y name campos 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, que aparecen en ese orden.

    Si decidi茅ramos ordenar esa matriz de personas por edad, no habr铆a garant铆a de que “Mike” aparecer铆a 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 de elecci贸n en el Kernel 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 min-heap es una estructura de datos basada en 谩rboles en la que cada node es m谩s peque帽o que todos sus hijos. La mayor铆a de las veces se utiliza un 谩rbol binario. Los montones tienen tres operaciones compatibles: delete_minimum(), get_minimum()y add().

    Solo puede eliminar el primer elemento del mont贸n, despu茅s de lo cual se “reordena”. Los montones se “reordenan” a s铆 mismos despu茅s de agregar o eliminar un elemento, de modo que el elemento m谩s peque帽o siempre est茅 en la primera posici贸n.

    Nota: Esto de ninguna manera significa que los montones sean matrices ordenadas. El hecho de que cada node 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 tema 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 clasifican 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 mantiene la matriz en un mont贸n, toma O (registro) tiempo, que es una operaci贸n muy eficiente.

    Implementaci贸n

    Ordenaci贸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 lo reordena posteriormente para que siga siendo un mont贸n. Se puede usar en una lista vac铆a.
    • heappop(list): Pops (elimina) el primer elemento (m谩s peque帽o) y devuelve ese elemento. El mont贸n sigue siendo un mont贸n despu茅s de esta operaci贸n, por lo que no tenemos que llamar 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:

    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))
    

    Salida:

    [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 luego las podemos sacar.

    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 funciones lambda.

    Sin embargo, dado que nuestra implementaci贸n se basa en los m茅todos de mont贸n integrados, 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 para simplemente 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 sorted() m茅todo.

    La 煤nica soluci贸n que nos queda para las clases personalizadas es anular los operadores de comparaci贸n. Esto lamentablemente nos limita a un solo tipo de comparaci贸n por clase. En nuestro ejemplo nos limita a ordenar Movie objetos por a帽o.

    Sin embargo, nos permite demostrar el uso de Heap Sort en clases personalizadas. Sigamos adelante y definamos el Movie clase:

    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 nuestro heap_sort() funci贸n:

    def heap_sort(array):
        heap = []
        for element in array:
            heappush(heap, element)
    
        ordered = []
    
        while heap:
            ordered.append(heappop(heap))
    
        return ordered
    

    Y finalmente, creemos una instancia de algunas pel铆culas, col贸quelas en una matriz y luego ord茅nelas:

    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)
    

    Salida:

    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

    Una de las principales razones por las que la ordenaci贸n de pila se sigue utilizando con bastante frecuencia, aunque a menudo se ve superada por una ordenaci贸n r谩pida bien implementada, es su fiabilidad.

    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 explotable en el peor de los casos 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 comportamiento incorrecto de O (n2) podr铆a desencadenarse f谩cilmente.

    Otro algoritmo con el que a menudo se compara la clasificaci贸n de mont贸n es la clasificaci贸n por combinaci贸n, que tiene la misma complejidad de tiempo.

    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 se puede implementar mucho m谩s f谩cilmente en el lugar que Merge Sort, por lo que se prefiere 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 (adem谩s de ser inestable) lo convierte en un gran algoritmo para usar donde 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 aprovechando la funcionalidad incorporada proporcionada 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.

     

    Etiquetas:

    Deja una respuesta

    Tu direcci贸n de correo electr贸nico no ser谩 publicada. Los campos obligatorios est谩n marcados con *