Iterating over an SPLHeap appears to remove entries from the heap

SPLHeap_Issue.md

Trying a little experiment with PHP's SPLHeap, but puzzled by the fact that iterating over the heap seems to be removing each entry as I access it.

The code

class ExtendedSPLHeap extends \SPLHeap {

    protected function compare($a, $b) {
        if ($a->latitude == $b->latitude) {
            return 0;
        }
        return ($a->latitude < $b->latitude) ? -1 : 1;
    }

}


$citiesHeap = new \ExtendedSPLHeap();

$file = new \SplFileObject("cities.csv");
$file->setFlags(SplFileObject::DROP_NEW_LINE | SplFileObject::SKIP_EMPTY);
while (!$file->eof()) {
    $cityData = $file->fgetcsv();
    if ($cityData !== NULL) {
        $city = new \StdClass;
        $city->name = $cityData[0];
        $city->latitude = $cityData[1];
        $city->longitude = $cityData[2];

        $citiesHeap->insert($city);
    }
}

echo 'There are ', $citiesHeap->count(), ' cities in the heap', PHP_EOL;

echo 'FROM NORTH TO SOUTH', PHP_EOL;
$citiesHeap->top();
while ($citiesHeap->valid()) {
    $city = $citiesHeap->current();

    echo sprintf(
        "%-20s %+3.4f  %+3.4f" . PHP_EOL,
        $city->name,
        $city->latitude,
        $city->longitude
    );

    $citiesHeap->next();
}

echo 'There are ', $citiesHeap->count(), ' cities in the heap', PHP_EOL;

and a sample of my cities.csv file

Birmingham,52.4800,-1.9100
Bristol,51.4600,-2.6000
Leeds,53.8100,-1.5500
Liverpool,53.4167,-3.0000
London,51.5171,-0.1062
Manchester,53.4800,-2.2400
Newcastle upon Tyne,54.9833,-1.5833

The output is

There are 7 cities in the heap
FROM NORTH TO SOUTH
Newcastle upon Tyne  +54.9833  -1.5833
Leeds                +53.8100  -1.5500
Manchester           +53.4800  -2.2400
Liverpool            +53.4167  -3.0000
Birmingham           +52.4800  -1.9100
London               +51.5171  -0.1062
Bristol              +51.4600  -2.6000
There are 0 cities in the heap

What puzzles me is that there are 0 entries remaining in the heap after that initial iteration over it; I'd expected that I could rewind and reiterate, but it seems my code is actually extracting the entries or otherwise removing the objects from each node of the tree as I retrieve them.

---

With further investigation (and help from nikic), it would appear that the next() method doesn't simply traverse the node pointers, but actually removes the current node from the heap as well.

This is not how a heap should behave, and surely adds extra overhead (the actual removal of the element and subsequent adjustment of all affected node pointers) to traversing the tree. Only the extract() method should remove nodes; and the rewind() method is rendered meaningless as a result.

Looks like it's given me my next project for core PHP.