Archivos diarios: 06/09/2017

1 entrada

Heap min max montículos

PrEDA: cómo programar montículos mínimos o máximos de cualquier tipo de objetos

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 […]