¿Es un PHP SplHeap realmente un montón?

Question

¿La implementación PHP de un Heap realmente es una implementación completa?

Cuando leí este artículo, http://en.wikipedia.org/wiki/Heap_%28data_structure%29, tengo la idea de que un nodo hijo tiene un elemento primario específico y que un elemento primario tiene elementos secundarios específicos.

Cuando miro el ejemplo en la documentación de PHP sin embargo, http://au.php.net/manual/en/class.splheap.php, parece que los nodos secundarios todos comparten el mismo 'nivel', pero la información padre/hijo específico no es importante.

Por ejemplo, ¿qué nodo es el padre de cada uno de los tres nodos que se encuentran en el puesto 10 en el ejemplo de PHP?

En mi aplicación, cuando un usuario selecciona 'nodo 156', necesito saber quiénes son sus hijos para que pueda pagarles una visita. (Podría hacer sus identidades 'nodo 1561', 'nodo 1562', etc., por lo que la relación es obvia).

¿La implementación de Heap PHP está incompleta? ¿Debo olvidarme de la clase Spl y seguir mi propio camino? ¿O me estoy perdiendo algo acerca de cómo deben funcionar los montones? ¿O tal vez debería estar mirando una variante de montón particular?

Gracias montones!

Answer 1

Un Heap se utiliza generalmente para responder preguntas que giran en torno a "¿cuál es el elemento max/min en el conjunto".

Mientras que un montón podría responder eficientemente "¿quiénes son los hijos del nodo máximo/mínimo?", Un montón no se destaca como una buena estructura de datos para usar cuando necesita acceder a un nodo arbitrario para responder su pregunta (un nodo que no es el nodo máximo). Tampoco es la estructura de datos para usar si hay relaciones padre-hijo específicas que necesitan ser representadas y mantenidas, porque los hijos pueden intercambiarse entre diferentes nodos principales.

Así que la implementación del montón de php definitivamente no está incompleta por estos motivos. Simplemente necesita una estructura de datos diferente.

Answer 2

La API para esta implementación de heap no permite el acceso a la matriz, que es lo que necesita en este caso. Los montículos se utilizan generalmente para implementar otras estructuras que le permiten eliminar fácilmente elementos de la parte superior.

Puede crear un iterador de envoltura que busque las posiciones que necesita. Sospecho que esta sería una solución de bajo rendimiento y no muy buena.

---

En esta situación, un BinaryTree es lo que creo que es necesario. Dado un lugar en el árbol puedes bajar sus hijos porque están directamente vinculados. Tengo un BinarySearchTree que mantendrá ordenado el árbol y puede llamar al getRoot para obtener una copia del BinaryTree. También hay un AvlTree que mantendrá el árbol equilibrado para una búsqueda óptima.