Is a PHP SplHeap really a Heap?

Question

Is the PHP implementation of a Heap really a full implementation?

When I read this article, http://en.wikipedia.org/wiki/Heap_%28data_structure%29, I get the idea that a child node has a specific parent, and that a parent has specific children.

When I look at the example in the PHP documentation however, http://au.php.net/manual/en/class.splheap.php, it seems that child nodes all share the same 'level', but the specific parent/child information is not important.

For example, which node is the parent for each of the three nodes who are ranked 10th in the PHP example?

In my application, when a user selects 'node 156', I need to know who its children are so that I can pay them each a visit. (I could make their identities 'node 1561', 'node 1562', etc, so the relationship is obvious).

Is the PHP Heap implementation incomplete? Should I forget the Spl class and go my own way? Or am I missing something about how heaps should operate? Or perhaps I should be looking at a particular heap variant?

Thanks heaps!

Answer 1

The API for this heap implementation does not allow array access, which is what you need in this case. Heaps are typically used to implement other structures that allow you to easily remove items from the top.

You could create a wrapper iterator that seeks to the positions you need. I suspect that this would be a poorly performing solution and not a very good one.

---

In this situation, a BinaryTree is what I think you need. Given a spot in the tree you can go down it's children because they're directly linked. I do have a BinarySearchTree that will keep the tree ordered and you can call getRoot to get a copy of the BinaryTree. There's also an AvlTree which will keep the tree balanced for optimal searching.

Answer 2

A Heap is usually used to answer questions that revolve around "what is the max/min element in the set".

While a heap could coincidentally efficiently answer "who are the children of the max/min node", a heap doesn't stand out as a good data structure to use when you need to access an arbitrary node to answer your question(a node that isn't the max node). It's also not the data structure to use if there are specific parent child relationships that need to be represented and maintained, because the children can and do get swapped between different parent nodes.

So php's heap implementation is definitely not incomplete on these grounds. You simply need a different data structure.