What's the difference between SplHeap, SplMinHeap, SplMaxHeap and SplPriorityQueue

Question

Have a bunch of objects I need to go through in a sorted order. Discovered the two sub-classes of SplHeap, SplMaxHeap and SplMinHeap, so figured I could try to use those as an experiment. In a comment I also read SplPriorityQueue mentioned.

However, after trying them out, I'm a bit unsure exactly what the difference between the three heaps are, and how to choose between the heaps and the queue.

Here are "4" classes, that all will sort objects by name, i.e. a foreach loop will list the objects in correctly sorted order, from first to last:

class SortedObjectHeap extends SplHeap|SplMinHeap|SplMaxHeap
{
    protected $_property;
    public function __construct(string $property)
    {
        $this->_property = $property;
    }
    protected function compare($x, $y)
    {
        $x = $x->{$this->_property} ?? null;
        $y = $y->{$this->_property} ?? null;    
        return strnatcasecmp($x, $y) * -1;
    }
}

$list = new SortedObjectHeap('name');
$list->insert($object);
// ...

class SortedObjectQueue extends SplPriorityQueue
{
    public function compare($x, $y)
    {
        return strnatcasecmp($x, $y) * -1;
    }
}

$list = new SortedObjectQueue();
$list->insert($object, $object->name);
// ...

Questions:

1. For the SortedObjectHeap the order looks to be exactly the same, no matter whether I extend SplHeap, SplMaxHeap or SplMinHeap. I thought the order would reverse when switching between Min and Max, but that does not seem to happen... so what really is the difference between extending these 3 classes?

2. From the docs, an obvious difference between SplHeap and SplPriorityQueue is that the queue takes an extra $priority parameter in the insert method. So, it seems with the queue you have to tell it what to sort by on each insert, while with a heap it "knows" this internally... Is that the difference, or are there other important differences between these two? I assume they maybe work differently internally? How do one choose between these two?

Answer 1

The reason that SplMinHeap and SplMaxHeap return the same order is that you're giving them both the same comparison function. But SplMinHeap::Compare and SplMaxHeap.Compare are defined differently.

SplMinHeap::Compare returns a positive integer if value1 < value2, SplMaxHeap::Compare returns a positive integer if value1 > value2.

You use SplMinHeap or SplMaxHeap if you want a heap that's ordered by the item's "natural" ordering. Like you want to create an ordered list of strings. Which one you use depends on if you want things in ascending or descending order.

You use SplPriorityQueue if you want to associate a priority with each item, and have the heap ordered by priority. For example, you have a bunch of names but you want them arranged in the order in which they were inserted into the system. So of Joe, Billy, Mary, and Alice showed up in that order, you'd give Joe priority 1, Billy priority 2, etc.

But if all you want is a sorted list of strings, why not just sort them and be done with it? That's going to be faster than populating a heap and extracting items one at a time.