I am using an SplHeap to hold graph nodes of a tree with directed edges that will be traversed from the leaves to the root. For this, I precalculate the "fan-in" of nodes and put them into the heap so that I can always retrieve the node with the smallest fan-in (0) from it.

After visiting a node, I reduce the fan-in of its successor by 1. Then obviously, the heap needs to be recalculated because the successor is now in the wrong place there. I have tried recoverFromCorruption(), but it doesn't do anything and keeps the heap in the wrong order (node with larger fanIn stays in front of smaller fanIn).

As a workaround, I'm now creating a new heap after each visit, amounting to a full O(N*log(N)) sort each time.

It should be possible, however, to make up-heap operations on the changed heap entry until it's in the right position in O(log(N)).

The API for SplHeap doesn't mention an up-heap (or deletion of an arbitrary element - it could then be re-added). Can I somehow derive a class from SplHeap to do this or do I have to create a pure PHP heap from scratch?

EDIT: Code example:

class VoteGraph {
    private $nodes = array();

    private function calculateFanIn() { /* ... */ }

    // ...

    private function calculateWeights() {
        $this->calculateFanIn();
        $fnodes = new GraphNodeHeap(); // heap by fan-in ascending (leaves are first)

        foreach($this->nodes as $n) {
            // omitted: filter loops
            $fnodes->insert($n);
        }

        // traversal from leaves to root
        while($fnodes->valid()) {
            $node = $fnodes->extract(); // fetch a leaf from the heap
            $successor = $this->nodes[$node->successor];
            // omitted: actual job of traversal
            $successor->fanIn--; // will need to fix heap (sift up successor) because of this

            //$fnodes->recoverFromCorruption(); // doesn't work for what I want
            // workaround: rebuild $fnodes from scratch
            $fixedHeap = new GraphNodeHeap();
            foreach($fnodes as $e)
                $fixedHeap->insert($e);
            $fnodes = $fixedHeap;
        }
    }
}

class GraphNodeHeap extends SplHeap {
    public function compare($a, $b) {
        if($a->fanIn === $b->fanIn)
            return 0;
        else
            return $a->fanIn < $b->fanIn ? 1 : -1;
    }
}