Una de las mejores formas de ordenar objetos es haciendo montículos. Está demostrado matemáticamente cómo mejoran la eficiencia de muchos tipos de algoritmos. Así que aquí traigo a modo de code-kata, de nuevo, otro pequeño script con el que se puede implementar montículos mínimos o máximos de cualquier tipo de objetos.
Un montículo es un tipo especial de árbol binario. Son binarios porque cada nodo tiene de máximo dos hijos. Además, éstos árboles están ordenados de arriba a abajo. Si es un montículo de mínimos entonces los elementos de arriba, los padres, siempre tienen un valor menor que los hijos. Si por el contrario es un montículo de máximos, entonces los elementos de arriba, los padres tienen un valor mayor.
De esta forma nos aseguramos que siempre tengamos el elemento mayor o menor en el nodo raiz del árbol. Esto es muy útil para utilizarlos en todo tipo de algoritmos de programación.
Punto de partida
En PHP tenemos una clase, que implementa mediante un vector interno, un montículo. Se trata de la clase SplHeap. Entonces simplemente tenemos que hacer herencia de SplHeap extendiendo la clase SplHeap. El código es bien sencillo:
<?php
define('NUMBER_OF_NODES', 30);
class TNodo
{
public $cost;
public $name;
}
class MyTNodesHeap extends SplHeap
{
public function compare($a, $b)
{
if ($a->cost < $b->cost) {
return 1; // a goes up
} elseif ($a->cost > $b->cost) {
return -1; // b goes down
} else {
return 0;
}
}
}
$heap = new MyTNodesHeap();
for ($i = 1; $i <= NUMBER_OF_NODES; ++$i) {
$obj = new TNodo();
$obj->cost = rand(1, 10);
$obj->name = 'Node '.$i;
$heap->insert($obj);
echo 'Inserted << '.$obj->name.' (cost '.$obj->cost.')'.PHP_EOL;
}
echo 'Inserted '.NUMBER_OF_NODES.' nodes.'.PHP_EOL;
for ($i=0; $i < NUMBER_OF_NODES; $i++) {
$obj = $heap->extract();
echo 'Extracted >> '.$obj->name.' (cost '.$obj->cost.')'.PHP_EOL;
}
Ya está, no tiene más. Gracias a esta clase que viene en PHP que ya tenemos implementado un montículo de mínimos. En este caso se trata de tener los nodos de mínimo coste arriba. Con lo que la función de comparación de nodos da como positivo el de menor coste.
Para hacer entonces un montículo de máximos simplemente modificamos la función compare() y a correr.
Terminando
Este script lo puedes poner en un fichero .php y ejecutarlo. Si todo va bien deberías de ver listados 30 elementos de menor a mayor coste. Algo parecido a esto:
