SplHeap、SplMinHeap、SplMaxHeap和SplPriorityQueue有什么区别

Question

有一堆我需要按排序顺序处理的对象。发现了SplHeap, SplMaxHeap and SplMinHeap, so figured I could try to use those as an experiment. In a comment I also read SplPriorityQueue mentioned.

的两个子类

但是，在试用之后，我有点不确定这三种堆到底有什么区别，以及如何在堆和队列之间进行选择。

这里是“4”类，所有对象都将按名称对对象进行排序，即 foreach 循环将按正确排序的顺序列出对象，从头到尾：

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);
// ...

问题：

对于 SortedObjectHeap，无论我扩展 SplHeap、SplMaxHeap 还是 SplMinHeap，顺序看起来都完全一样。我以为在 Min 和 Max 之间切换时顺序会颠倒，但这似乎并没有发生......那么扩展这 3 类?
从文档中可以看出，SplHeap 和 SplPriorityQueue 之间的一个明显区别是队列在 insert 方法中需要一个额外的 $priority 参数.因此，对于队列，您似乎必须告诉它在每次插入时根据什么进行排序，而对于堆，它 "knows" 这在内部......这就是区别，或者这两者之间还有其他重要区别吗？我假设他们可能在内部工作方式不同？这两者如何选择？

Answer 1

SplMinHeap 和 SplMaxHeap return 顺序相同的原因是您为它们提供了相同的比较函数。但是 SplMinHeap::Compare and SplMaxHeap.Compare 的定义不同。

SplMinHeap::Compare return 如果 value1 < value2 为正整数，SplMaxHeap::Compare return 如果 value1 > value2 为正整数。

如果您想要按项目 "natural" 排序的堆，则使用 SplMinHeap 或 SplMaxHeap。就像您想创建一个有序的字符串列表一样。你使用哪一个取决于你想要升序还是降序。

如果你想为每个项目关联一个优先级，你可以使用 SplPriorityQueue，并让堆按优先级排序。例如，你有一堆名字，但你希望它们按照它们被插入系统的顺序排列。所以乔、比利、玛丽和爱丽丝按这个顺序出现，你给乔优先 1，比利优先 2，等等

但是，如果您只需要一个排序的字符串列表，为什么不直接对它们进行排序并完成呢？这比填充堆并一次提取一个项目要快。

SplHeap、SplMinHeap、SplMaxHeap和SplPriorityQueue有什么区别

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

php

heap

spl

priority-queue

data-structures