如何剥离或切片SplHeap（也是SplMaxHeap，SplMinHeap）的底部项目？

Question

I have a SplMaxHeap with 30 items. Now I want to strip the last 10 ones. How to do this in a decent and efficient way?

The only solutions I see so far is to copy the first 20 items to a new heap or to convert the heap to an array, use the array_slice and put them also in a new heap.

I even can't see a way to get something out of the heap not from the top.

I guess the reason for this is a limitation of the general design of a heap? I was also thinking to use a DoublyLinkedList, however there I am missing the automatic sorting.

Answer 1

One approach is to create a new class derived from an SPL heap, which upon insert only keeps the top (or bottom, depending on the heap) n items.

A super-basic example might look something like:

class Top100 extends SplMinHeap
{
    protected $limit = 100;
    public function insert($value)
    {
        parent::insert($value);
        while (count($this) > $this->limit) {
            $this->extract();
        }
    }
}

This is discussed further in Tobias Schlitt's 2010 article "Heap, heap, hooray!".