9

我正在使用一个SplHeap来保存具有从叶子到根的有向边的树的图形节点。为此，我预先计算了节点的“扇入”并将它们放入堆中，以便我始终可以从中检索具有最小扇入 (0) 的节点。

访问一个节点后，我将其后继节点的扇入减少 1。那么显然，堆需要重新计算，因为后继节点现在位于错误的位置。我试过recoverFromCorruption()了，但它什么也没做，并且使堆保持错误的顺序（较大的节点fanIn停留在较小的前面fanIn）。

作为一种解决方法，我现在在每次访问后创建一个新堆，每次进行一次完整的 O(N*log(N)) 排序。

但是，应该可以对更改的堆条目进行堆堆操作，直到它位于 O(log(N)) 中的正确位置。

的 APISplHeap没有提到上堆（或删除任意元素 - 然后可以重新添加）。我可以以某种方式派生一个类SplHeap来执行此操作，还是必须从头开始创建一个纯 PHP 堆？

编辑：代码示例：

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;
    }
}

完整代码也可用：https ://github.com/md2k7/civicracy/blob/master/civi-php/protected/components/VoteGraph.php#L73

编辑 2：

$this->putNode(new GraphNode(4));
$this->putNode(new GraphNode(1, 2));
$this->putNode(new GraphNode(3, 2));
$this->putNode(new GraphNode(2, 4));

这意味着用户 1和用户 3正在为用户 2投票，用户 2正在为用户 4投票，通过了 3 票（2 票收到 + 他/她自己的票）。这被称为委托投票：我的算法是“从底部”（叶子）传递投票，我已经知道每个用户有多少权重（责任/代表/你喜欢......）。

4

2 回答 2

1

更改值后不能重新插入更新的节点吗？

$successor->fanIn--;
$fnodes->insert($updatedNode);

插入不会强制对堆进行重新排序吗？这将是一个较低的订单，然后创建一个新订单。

于 2012-11-13T16:56:24.173 回答
1

我最近正在解决非常类似的问题，似乎 SPL 不支持更新。所以

我不得不写我自己的堆。

它效率不高，但它可以满足我的需要，并且比重复排序数组要快得多……尽管 SPL 堆仍然快得多……

这里是...

class heap
{
    public $members=array();

    // these two are just for statistics
    private $swaps=0; 
    private $recurs=array('lups'=>0, 'ldowns'=>0);

    public function insert($val){

        if(is_array($val) && empty($this->members)){ // because heapify is (in theory) more efficient
            foreach($val as $v){
                $this->members[]=$v;
            }
            $this->heapify();
        }else{
            $emptyPosition=count($this->members);  // count(members) gets index of first empty position, not last key
            $this->members[]=$val; // puts $val in
            $this->ladderup($emptyPosition);
        }
    }

    public function heapify(){
    /* in case all the heap is broken, we can always use this to repair it.
     It should be more efficient to fill $members randomly and "repair" it with heapify after,
     than inserting things one by one*/

        $start=max(0, floor( (count($this->members)-1)/2)); // find last parent
        for($i=$start;$i>=0;$i--){
            $this->ladderdown($i);
        }
    }

    private function ladderdown($index){
    // recursively sifts down $index
        $this->recurs['ldowns']++;

        /*
        indexes of children
        they are stored at  parent_position*2 and parent_position*2+1
        but becouse php uses null-based array indexing, we have to modify it a little
        */  
        $iA=$index*2+1; 
        $iB=$index*2+2;

        if($iA<count($this->members)){ // check if children exist
            if($iB<count($this->members)){
                if($this->compare($iA, $iB)>=0) $bigger=$iA; // if both exist, compare them, cause we want to swap with the bigger one ; I'm using ">=" here, that means if they're equal, left child is used
                else $bigger=$iB;
            }else{
                $bigger=$iA; // if only one children exists, use it
            }

            if($this->compare($bigger, $index)>0){ // not using ">=" here, there's no reason to swap them if they're same
                $this->swap($bigger, $index);
                $this->ladderdown($bigger); // continue with $bigger because that's the position, where the bigger member was before we swap()ped it 
            }
        }
    }

    private function ladderup($index){
    // sift-up, 
        $this->recurs['lups']++;

        $parent=max(0, floor( ($index-1)/2)); // find parent index; this way it actualy swaps one too many times: at the end of sift-up-ing swaps the root with itself
        if($this->compare($index, $parent)>0){
            $this->swap($index, $parent);
            $this->ladderup($parent);
        }
    }

    public function root(){
        if(count($this->members)){
            return $this->members[0];
        }
        return false;   
    }

    public function extract(){
    // removes and returns root member
        if(!count($this->members)) return false;

        $this->swap(0,count($this->members)-1); // swaps root with last member
        $result=array_pop($this->members); // removes last member (now root)
        $this->ladderdown(0); // root is on wrong position, sifts it down
        return $result;
    }

    public function update($index, $value){
        if($index<count($this->members)){
            $this->members[$index]=$value;
            $this->ladderup($index);
            $this->ladderdown($index);
        }
    }

    public function delete($index){
    // removes index from heap the same way as root is extracted
        $this->swap(count($this->members)-1, $index); // swaps index with last one
        array_pop($this->members);
        $this->ladderup($index);
        $this->ladderdown($index);
    }

    private function swap($iA, $iB){
    // swaps two members
        $this->swaps++;

        $swap=$this->members[$iA];
        $this->members[$iA]=$this->members[$iB];
        $this->members[$iB]=$swap;
    }

    private function compare($iA, $iB){
        $result=$this->members[$iA] - $this->members[$iB];
        return $result;
    }

    public function stats($text=""){
     // prints and resets statistics
        echo "STATS: $text... Sift-ups: ".$this->recurs['lups']." Sift-downs: ".$this->recurs['ldowns']." Swaps: ".$this->swaps." <br>";
        $this->recurs=array('lups'=>0, 'ldowns'=>0);
        $this->swaps=0;
    }
}

//here's how to use it...

$h=new heap;

for($i=0; $i<10000; $i++){
    $h->insert(rand(1,1000));
}
$h->stats("after inserting one-by-one");

while($biggest=$h->extract()); // note that $h->extract might return FALSE, but might return zero as well, if there was zero in the heap

$h->stats("after extracting all roots (like in heapsort)");

echo "Now, heap is empty. Let's try whole array at once <br>";

for($i=0; $i<10000; $i++){
    $a[]=rand(1,1000);
}
$h->insert($a); // inserting whole array here, so heap will use more efficient heapify()
$h->stats("after heapify");

echo "let's update two indexes<br>";

$h->update(1234,44444);// sure on top
$h->stats("after update");
$h->update(8888,40000);// second place
$h->stats("after update");

echo "extract biggest three indexes<br>";

echo $h->extract()." - this should be 44444<br>";
echo $h->extract()." - this should be 40000<br>";
echo $h->extract()." - this should be biggest number given by rand(1,1000)<br>";

$h->stats("after three extracts");

while($h->extract());
$h->stats("after extracting the rest");

结果是：

STATS：一一插入后... Sift-ups：22651 Sift-downs：0 Swaps：12651
STATS：提取所有根后（如在堆排序中）... Sift-ups：0 Sift-downs：116737 Swaps : 116737
现在，堆是空的。让我们一次尝试整个数组
STATS：heapify 后... Sift-ups：0 Sift-downs：12396 Swaps：7396
让我们更新两个索引
STATS：更新后... Sift-ups：11 Sift-downs：1 Swaps：10
统计：更新后... 筛选：13 筛选：1 交换：12
提取最大的三个索引
44444 - 这应该是 44444
40000 - 这应该是 40000
1000 - 这应该是 rand(1,1000) 给出的最大数字)
统计数据：经过三次提取...筛选：0 筛选：42 交换：42
统计：提取其余部分后...筛选：0 筛选：116652 交换：116652

您将不得不对其进行一些修改，但无论如何，希望它有所帮助..

于 2012-11-18T22:18:26.783 回答