Как раздеть или нарезать нижние элементы SplHeap (также SplMaxHeap, SplMinHeap)?
у меня есть SplMaxHeap с 30 предметов. Теперь я хочу раздеть последние 10. Как сделать это достойно и эффективно?
Единственное решение, которое я пока вижу, это скопировать первые 20 элементов в новую кучу или перерабатывать куча к массиву, используйте array_slice и положить их также в новую кучу.
Я даже не вижу способа вытащить что-то из кучи не сверху.
Я предполагаю, что причиной этого является ограничение общего дизайна кучи? Я также думал использовать DoublyLinkedList, однако там мне не хватает автоматической сортировки.
Решение
Один из подходов заключается в создании нового класса, производного от кучи SPL, который при вставке сохраняет только верх (или низ, в зависимости от кучи) N Предметы.
Супер базовый пример может выглядеть примерно так:
class Top100 extends SplMinHeap
{
protected $limit = 100;
public function insert($value)
{
parent::insert($value);
while (count($this) > $this->limit) {
$this->extract();
}
}
}
Это обсуждается далее в статье Тобиаса Шлитта 2010 года «Куча, куча, ура!».
Другие решения
Проблема в том, что внутри SPLHeap нет «дна». Элементы хранятся в древовидной структуре. Термин «низ» становится немного бессмысленным, однако всегда есть «верх» дерева, и это именно то, что может вернуть SPLHeap.
Если у вас есть небольшое количество элементов, вам могут сойтись альтернативные структуры данных (даже простых массивов будет достаточно). Вставка элементов может занять немного больше времени (здесь деревья более эффективны), но поддержание верха и низа снова дешево (например, SplDoubleLinkedList).
Если вы не храните десятки тысяч элементов, вы можете пропустить SplHeap для этого.
Примечание: достаточно просто создать структуру fixedHeap в самом PHP, но я считаю, что это не будет быстрее. Тест, чтобы проверить, что удовлетворяет ваши потребности.