В чем разница между SplHeap, SplMinHeap, SplMaxHeap и SplPriorityQueue

У меня есть куча объектов, которые мне нужно пройти в отсортированном порядке. Обнаружены два подкласса SplHeap, SplMaxHeap и SplMinHeap, поэтому я решил использовать их в качестве эксперимента. В комментарии я также прочитал SplPriorityQueue упоминается.

Однако, попробовав их, я немного не уверен, в чем именно разница между тремя кучами и как выбирать между кучами и очередью.

Вот «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);
// ...

Вопросы:

  1. Для SortedObjectHeap порядок выглядит точно таким же, независимо от того, расширяю ли я SplHeap, SplMaxHeap или SplMinHeap. Я думал, что при переключении между Min и Max порядок изменится на противоположный, но, похоже, этого не происходит... так в чем же на самом деле разница между расширением этих трех классов?

  2. Из документов очевидная разница между SplHeap и SplPriorityQueue заключается в том, что очередь принимает дополнительный параметр $priority в методе insert. Итак, кажется, что с очередью вы должны сказать ей, что сортировать при каждой вставке, в то время как с кучей она «знает» это внутренне ... В этом разница или есть другие важные различия между этими двумя? Я предполагаю, что они могут работать по-разному внутри? Как выбрать между этими двумя?


person Svish    schedule 12.11.2017    source источник


Ответы (1)


Причина, по которой SplMinHeap и SplMaxHeap возвращают один и тот же порядок, заключается в том, что вы даете им одну и ту же функцию сравнения. Но SplMinHeap::Compare и SplMaxHeap.Compare определяются по-разному.

SplMinHeap::Compare возвращает положительное целое число, если value1 < value2, SplMaxHeap::Compare возвращает положительное целое число, если value1 > value2.

Вы используете SplMinHeap или SplMaxHeap, если вам нужна куча, упорядоченная в соответствии с «естественным» порядком элемента. Например, вы хотите создать упорядоченный список строк. Какой из них вы используете, зависит от того, хотите ли вы что-то в порядке возрастания или убывания.

Вы используете SplPriorityQueue, если хотите связать приоритет с каждым элементом и упорядочить кучу по приоритету. Например, у вас есть куча имен, но вы хотите расположить их в том порядке, в котором они были введены в систему. Итак, если Джо, Билли, Мэри и Алиса появились в таком порядке, вы бы дали Джо приоритет 1, Билли приоритет 2 и т. д.

Но если все, что вам нужно, это отсортированный список строк, почему бы просто не отсортировать их и покончить с этим? Это будет быстрее, чем заполнять кучу и извлекать элементы по одному.

person Jim Mischel    schedule 13.11.2017
comment
Ах, так что я бы использовал SplMinHeap/SplMaxHeap, если бы существовал естественный порядок, которым я мог бы воспользоваться, но если я переопределю метод compare, я мог бы также расширить SplHeap? И да, я полагаю, отсортированный список строк был чем-то вроде чрезмерного упрощения... На самом деле это объекты, которые я собираю полуслучайно, а затем мне нужно обработать их в определенном порядке. Я мог сначала собрать, а потом сделать сортировку, но искал способ не делать это за 2 шага, в основном из любопытства :) - person Svish; 13.11.2017
comment
@Свиш: Да. Если вы собираетесь переопределить compare, вам следует использовать SplHeap. - person Jim Mischel; 13.11.2017