Ordenar montón en Python

O

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.

 

About the author

Ramiro de la Vega

Bienvenido a Pharos.sh

Soy Ramiro de la Vega, Estadounidense con raíces Españolas. Empecé a programar hace casi 20 años cuando era muy jovencito.

Espero que en mi web encuentres la inspiración y ayuda que necesitas para adentrarte en el fantástico mundo de la programación y conseguir tus objetivos por difíciles que sean.

Add comment

Sobre mi

Últimos Post

Etiquetas

Esta web utiliza cookies propias para su correcto funcionamiento. Al hacer clic en el botón Aceptar, aceptas el uso de estas tecnologías y el procesamiento de tus datos para estos propósitos. Más información
Privacidad