Max/Min heap, priority queues… ¿Qué son y cómo lo hago? Comparativa Python, C/C++.


Introducción al algoritmo. ¿Porqué es útil?


Heapsort es el nombre que se le da a un tipo de algoritmo de ordenación basado en trees o árboles y que opera con complejidad O(n\log_{}n). El algoritmo realiza se realiza in place, es decir, sólo un número constante de elementos del array se almacenan fuera del mismo durante la ejecución del algoritmo.

Este algoritmo hace uso de un tipo de estructura de datos llamada “heap” para manejar la información, como veremos más abajo el uso de heaps permite implementar una cola de prioridad muy eficiente.


Como dijo Jack…


Aviso a navegantes: huelga decirlo, pero al igual que en el resto de posts, agradeceré cualquier mejora o corrección sobre la entrada.

Una binary-heap (me tomaré la licencia de no usar la traducción del término como montículo binario) es un tipo de estructura de datos que trata de representar un array en forma de árbol binario semicompleto (el término anglosajón es nearly complete binary tree).

Cada elemento del array constituye un nodo del árbol, que tendrá todos sus nodos completos excepto, opcionalmente, el último de los nodos.

Un array A que representa nuestro heap tiene dos parámetros, a saber:

  • A.length: longitud del array, es decir, el número de elementos que podemos almacenar.
  • A.size: número de elementos contenidos en el array.

Si la raíz (root) del árbol se encuentra en A[1], dado el índice i de un nodo podremos calcular el índice de su padre y sus hijos (derecho e izquierdo).

  • Parent = (\frac{2}{i})
  • Left = 2\cdot i
  • Right =2\cdot i+1

Paremos por un momento a reflexionar sobre el hecho de que la raíz del árbol se encuentre en A[1]. ¿Porqué sucede esto cuando todos los lenguajes de programación que conozco comienzan a indexar los arrays a partir del índice 0? Podemos alegar, como yo hice al leer el algoritmo, que son cosas del pseudocódigo pero hay una razón más sutil: la optimización. El hecho de colocar nuestra raíz en A[1] y no en A[0] simplifica las fórmulas anteriores de forma notable (puedes deducirlas rápidamente). Puede parecer insignificante, pero no lo es cuando buscamos eficiencia.

Según la bibliografía, las implementaciones eficientes de algoritmos heapsort codifican estas operaciones como macros o procedimientos inline y calculan los índices a nivel de bit. Como veremos más abajo este hecho introduce una mejora en el rendimiento.

Como adelanta la introducción, uno de los usos más comunes de los heaps es construir una cola de prioridad (priority queue). Las hay de dos tipos; max y min, o más comúnmente max-heap o min-heap.

Ambos tipos de heaps satisfacen una propiedad llamada heap property (imaginativo, ¿verdad?) que queda resumida de la siguiente manera:

  • Max-heap: A[Parent(i) <= A[i]
  • Min-heap: A[Parent(i) >= A[i]

Esta regla no es más que un criterio de ordenación que determina si los valores se ordenan desde la raíz a las hojas de mayor a menor, max-heap, o viceversa, min-heap.

Ciertos funciones, o métodos, son necesarios para crear y mantener nuestra estructura. De ahora en adelante trataremos exclusivamente con min-heaps, pero tanto los procedimientos como las conclusiones serán análogas a las max-heaps. Vamos con ellos:

  • Min-Heapify: Una función que se encarga de mantener la propiedad de min-heap y que opera en tiempo O(log_{}n). Es el alma del algoritmo.
  • Build-Heap: en tiempo lineal genera el min-heap a partir de un array de entrada. Podemos pensar en ella como un constructor que recibe el array a ordenar como parámetro.
  • Heap-Sort: ordena el array in place en O(nlog_{}n)
  • Heap-insert, Heap-extract-min, Heap-increase-key: rutinas de complejidad O(log_{}n) que nos permiten interaccionar con la cola; extraer, insertar y modificar elementos.

Así contado puede no tener demasiado sentido, se comprende mejor con unos esquemas o un vídeo, podéis ver este:



Ahora ya queda claro que el principio básico del heap es mantener la propiedad de los heaps, es decir, que el nodo inferior siempre sea mayor que el padre en una cola de prioridad mínima y al revés en el caso de máxima prioridad.


¿Vamos ya con el código?

No he encontrado en internet mucho sobre la implementación de una priority queue en C, seguramente porque los lenguajes más modernos las incorporan en sus librerías estándar. Así que he tenido que implementarla casi desde cero mirando algunos ejemplos.

Las sorpresas las dejo para el final, así que primero vamos con C++ y con Python.

Como vamos a ver ahora, implementar los heaps en C++ es bastante sencillo, dejo aquí la implementación más rápida entre las que he probado, adaptada desde el código de cplusplus.com.

#include <queue>
#include <functional>
#include <ctime>
#include <iostream>
#include <math.h>

using namespace std;

int main(int argc, char* argv[])
{
    srand(time(0));

    int elements;
    int *values = (int*)malloc(sizeof(int)*elements);

    for (int j = 0; j < 9; ++j)
    {

        elements = pow(10,j);
        int *values = (int*)malloc(sizeof(int)*elements);
        // Generamos un array de elementos enteros
        for( int i = 0; i != elements; ++i ) {
            values[i] = rand();
        }

        // Construimos la cola a partir del array
        std::priority_queue<int, std::vector, std::greater > mypq (values, values+elements);

        // Extraemos los elementos uno a uno
        for (int i = 0; i < elements; ++i)
        {
            mypq.pop();
        }
    }
    return 0;
}


Y la de Python es aún más simple, como nos tiene acostumbrados:

import numpy as np
import heapq
import sys
import time

time_heapify = np.zeros(8)
time_extract = np.zeros(8)

for i in range(8):
    elements = pow(10,i)
    # Creamos una lista de enteros
    a = list(np.random.randint(low=sys.maxint, size=elements))
    # Transformamos el array de enteros en una heapq
    heapq.heapify(a)

    for j in range(elements):
        # Extraemos el elemento minimo
        heapq.heappop(a)


Resultados, una de carreras.


Los resultados son interesantes, no me esperaba que el programa en C++ distara tanto del programa en C. C marca la diferencia incluso sin optimizar.

3 lang. insert()

Se repite el mismo escenario que el caso anterior, C marca la diferencia…

3lengExtract


Optimizaciones implementadas sobre el programa en C.


He implementado algunas mejoras básicas sobre el programa en C y los resultados los podéis ver resumidos aquí:

extractc
insert() min-heap in c

  • El programa básico ya parte con su raíz en A[1], por lo que no podremos apreciar la reducción de tiempo que introduce esa mejora.
  • El siguiente paso ha sido sustituir las expresiones de Parent, Left y Right por sus operaciones a nivel bit (operadores >>, << y | ) e implementarlas como macros.
  • El tercer paso consiste en emplear registros para algunas variables que se usan a menudo y hacer algunas funciones clave inline.
  • El paso más significativo es la optimización agresiva del compilador, sólo para ver que marca la diferencia la he incluido aquí.


Notas finales.


Puede que los tiempos no reflejen el rendimiento que la aplicación pueda ofrecer en condiciones óptimas ya que las he realizado en mi ordenador personal, si todo va bien en un par de meses probaré la aplicación completa en el centro de computación y realizaré unos benchmarks más adecuados.

La versión de C definitiva la dejaré en Github en breves, tengo que terminar alguna prueba más! (;

Los datos sobre las versiones del compilador g++ empleado tanto para C como para C++:

i686-apple-darwin11-llvm-g++-4.2

Y la versión de Python; Python

Python 2.7.5 :: Anaconda 1.7.0 (x86_64)

Esta entrada fue publicada en Algoritmos, C/C++, python y etiquetada , , , , , , , , . Guarda el enlace permanente.

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s