PrEDA: el algoritmo de ordenamiento Heapsort

De nuevo traigo a modo de code-kata otro algoritmo de programación. En este caso no se usa ninguna técnica avanzada de programación. Sino que simplemente se usa el algoritmo de ordenamiento Heapsort, que como su nombre indica, se sirve de un heap (montículo) para hacer el ordenamiento.

Como ya hablé en este otro post sobre los montículos, he reutilizado el código para hacer un par de clases genéricas que nos pueden servir para construir algoritmos más avanzados.

PHP ya nos provee de una clase que implementa un montículo, el SplHeap. También tenemos en PHP una clase para un SplMinHeap y SplMaxHeap. Pero no podemos controlar cómo hacemos la valoración de mínimo o máximo para poner arriba del montículo los objetos ordenados. Así que no queda más remedio que extender la clase que nos provee PHP.

Los objetos que ordenamos

Aquí dejo los objetos que implementan tanto el montículo de mínimos como el de máximos:

<?php

class TNodo
{
    private $cost; // This is de value used for sorting.
    private $string; // The object stored is a simple String.

    public function setCost($cost)
    {
        $this->cost = $cost;
    }

    public function getCost()
    {
        return $this->cost;
    }

    public function setString($string)
    {
        $this->string = $string;
    }

    public function __toString()
    {
        return $this->string;
    }
}

class MyTNodesMinHeap extends SplHeap
{
    public function compare($a, $b)
    {
        if ($a->getCost() < $b->getCost()) {
            return 1; // a is better, goes up
        } elseif ($a->getCost() > $b->getCost()) {
            return -1; // b is better
        } else {
            return 0;
        }
    }
}

class MyTNodesMaxHeap extends SplHeap
{
    public function compare($a, $b)
    {
        if ($a->getCost() > $b->getCost()) {
            return 1; // a is better, goes up
        } elseif ($a->getCost() < $b->getCost()) {
            return -1; // b is better
        } else {
            return 0;
        }
    }
}

Ambos montículos almacenan objetos de tipo TNodo. Y se hace el ordenamiento en función al cost de los objetos de tipo TNodo. Cada objeto TNodo podría ser por ejemplo una tarea que tiene un coste de tiempo. Así pues el montículo mínimo pone arriba el nodo de mínimo coste, y lo mismo con el máximo.

Estos objetos los he guardado en un fichero llamado dataStructure.heaps.php para luego reutilizarlos en el siguiente código.

Ahora el ordenamiento Heapsort

Bien sencillo queda. Simplemente consiste en ir insertando en un montículo los nodos que tenemos en un vector inicial. Y al sacarlos del montículo ya van saliendo ordenados.

<?php

include 'dataStructure.heaps.php';

define('NUMBER_OF_NODES', 10);

$minheap = new MyTNodesMinHeap();
$maxheap = new MyTNodesMaxHeap();

for ($i = 1; $i <= NUMBER_OF_NODES; ++$i) {
    $obj = new TNodo();
    $obj->setCost(rand(1, 10));
    $obj->setString('Task '.$i);
    $minheap->insert($obj);
    $maxheap->insert($obj);
    echo 'Inserted << '.$obj.' (cost '.$obj->getCost().')'.PHP_EOL;

    if ($i == 5) {
        $obj->setString('String5 changed!');
    }
}

echo 'Inserted '.NUMBER_OF_NODES.' nodes.'.PHP_EOL;

echo 'Sorting with minheap:'.PHP_EOL;
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
    $obj = $minheap->extract();
    echo 'Extracted >> '.$obj.' (cost '.$obj->getCost().')'.PHP_EOL;
}
echo 'Sorting with maxheap:'.PHP_EOL;
for ($i = 0; $i < NUMBER_OF_NODES; ++$i) {
    $obj = $maxheap->extract();
    echo 'Extracted >> '.$obj.' (cost '.$obj->getCost().')'.PHP_EOL;
}

Cabe resaltar que los nodos en PHP no se copian a los montículos, sino que se añaden por referencia. Es decir que realmente sólo tenemos 10 objetos finalmente, que se ordenan de una forma o de otra. Así si editamos uno de los nodos, al listarlos con Heapsort estarán modificados tanto de una forma como de otra.

Terminando

Si todo ha ido bien, simplemente tienes que ver algo parecido a esto:

jaime@Vostro:~/project-preda-algorithms$ php basic.heapsort.php 
Inserted << Task 1 (cost 10)
Inserted << Task 2 (cost 8)
Inserted << Task 3 (cost 7)
Inserted << Task 4 (cost 5)
Inserted << Task 5 (cost 5)
Inserted << Task 6 (cost 7)
Inserted << Task 7 (cost 10)
Inserted << Task 8 (cost 4)
Inserted << Task 9 (cost 1)
Inserted << Task 10 (cost 3)
Inserted 10 nodes.
Sorting with minheap:
Extracted >> Task 9 (cost 1)
Extracted >> Task 10 (cost 3)
Extracted >> Task 8 (cost 4)
Extracted >> String5 changed! (cost 5)
Extracted >> Task 4 (cost 5)
Extracted >> Task 3 (cost 7)
Extracted >> Task 6 (cost 7)
Extracted >> Task 2 (cost 8)
Extracted >> Task 7 (cost 10)
Extracted >> Task 1 (cost 10)
Sorting with maxheap:
Extracted >> Task 1 (cost 10)
Extracted >> Task 7 (cost 10)
Extracted >> Task 2 (cost 8)
Extracted >> Task 6 (cost 7)
Extracted >> Task 3 (cost 7)
Extracted >> Task 4 (cost 5)
Extracted >> String5 changed! (cost 5)
Extracted >> Task 8 (cost 4)
Extracted >> Task 10 (cost 3)
Extracted >> Task 9 (cost 1)