Consider adding a Heap

[rtheunissen]

Would be a heap using an optional comparator function (max heap by default). PriorityQueue already uses a heap internally so we could extend that and create a dedicated implementation, potentially replacing PriorityQueue entirely.

[nikic]

I'm not clear on what the difference between a PriorityQueue and Heap is. Is it only the use of a custom comparison function?

[rtheunissen]

Yes, so you could easily use a heap as a priority queue. Iteration and removal would still be destructive (nature of a heap). The only difference API-wise would be that the priority would be determined by the element, rather than associated separately, which I don't like in the context of a priority queue. What if you wanted to add strings? You'd have to create a string+priority class, and compare that object->priority in the comparator. Would be cumbersome for what would be 9/10 of the use cases of a Heap.

However, like SPL, I'm wondering if a dedicated heap might be useful. The cost to implement and maintain would be small because PriorityQueue already is a heap internally. The question is really whether there is enough use cases for a heap that isn't a priority queue.

[rtheunissen]

@nikic interesting to see that Java's PriorityQueue is simply a heap with an optional comparator. So without the comparator it'd use <=> and be a normal max heap. But if the comparator is provided, you can do something like this to get a priority queue:

$pq = new Heap($values, function($a, $b) {
    return $a->priority <=> $b->priority;
});

What's nice about this is we get two structures in one. If we only have a priority queue, we don't have a heap at all, because the ordering is strictly determined by the integer priority. I'm still not convinced that there's a use case for a heap that isn't a priorityqueue though.

There's obviously also something to say for having to invoke the comparator for each comparison. If there is enough support for a dedicated heap, we could easily keep PriorityQueue as well, but they feel similar enough to avoid having both. It's worth keeping in mind that the comparator would only be invoked at most log(n) times for each push or pop.

One nice advantage of the comparator approach is that heap nodes wouldn't need the extra zend_long for the priority, and we can still use u2.next for the insertion order stamp. Would just be a zval* buffer rather than a ds_priority_queue_node_t* buffer.

As it stands I'm in favour of replacing PriorityQueue with a more flexible Heap.

[nikic]

@rtheunissen It may be reasonable to add an optional comparison callback, but I don't think it makes sense to remove the existing internal priority and implicit comparison for two reasons. One is obviously performance -- doing a (reentrant) function call is pretty slow. The second one is that this will hurt usability, because it effectively requires the priority queue to be intrusive, i.e. requires that the priority be stored on the elements in the queue. In some cases this may be reasonable, but in others this will require some gymnastics to use the pq. For example if you want elements to be part of multiple independent pqs and as such cannot store an intrusive priority you'd have to store tuples [$priority, $element] with comparator $a[0] <=> $b[0]. This is again both slow and hard to use.

[rtheunissen]

@nikic very good point re: multiple entries in the same queue. It would definitely be a step backward from an API / usability aspect. I do still like the idea of a comparator though. We could make the priority a zval, and have a comparator be optional. That way the user can define exactly how to interpret the given zval as a priority. Would use more memory per element though, but roughly equal to Set and Map.

[nikic]

@rtheunissen This is basically what SplPriorityQueue does iirc (only with comparison function as a class method, requiring inheritance ... bah!)

[rtheunissen]

@nikic that's true. If the queue is intrusive, and we take for example an object that has a priority property, what happens when that property changes? The queue wouldn't be aware, and the heap wouldn't be correct. You'd have to do something like $heap->validate().

For this reason, I'm wondering if this would work well:

• Explicit priority separate from the value itself.
• Priority can be a zval (not just an zend_long how it is currently)
• Can optionally set a callable comparator.

This would increase the memory usage from 24 bytes to 32 bytes per node (I think), and I assume I'll need to store the callable on the structure as well. If only we had a Comparable interface :[.

Unless we keep to strict integer priorities and don't expose the comparator, which takes us back to square one. Faster and less memory, but not as flexible. It's a tricky balance between use case and performance. This is why I was considering a separate heap structure, which wouldn't have an associated priority at all, and support a user comparator. It would be up to the user to ensure that the definition of the comparison doesn't rely on values that can change arbitrarily - or we can implement something similar to SPL's recoverFromCorruption. Maybe fix or heapify are nicer terms for the same thing.

[rtheunissen]

Having thought about this for a long time now, I think the best way forward is to keep the current API. The integer priority provides a mechanism for the user to the the pq as a heap, all they need to do is represent the value's position in the heap using an integer - the priority. This means that the priority remains a zend_long and there is no user comparison function.