Is there a way to make PHP's SplHeap recalculate? (aka: add up-heap to SplHeap?)
- by md2k7
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;
}
}
