时间戳

首页 > 解决方案 > 何时调用 SplHeap::isCorrupted？

php - 何时调用 SplHeap::isCorrupted？

问题描述

抽象类SplHeap提供了isCorrupted方法：

判断堆是否处于损坏状态

public SplHeap::isCorrupted ( void ) : bool

我想知道这种方法如何有用，更不用说堆如何损坏了。人们会期望内部堆实现是可靠的，并且永远不会被破坏。

起初我认为也许可以直接访问底层数组，这将允许这样的事情（类似于 Python 的heapq实现可能发生的事情）：

$heap = new SplMinHeap();
$heap->insert(9);
$heap->insert(5);

echo $heap->top(); // 5

$heap[0] = 10; // make the heap inconsistent? -- not possible

堆的内部数据结构原来是私有的。上述堆的A var_dump，呈现如下：

object(SplMinHeap)#1 (3) {
    ["flags":"SplHeap":private]=>int(0)
    ["isCorrupted":"SplHeap":private]=>bool(false)
    ["heap":"SplHeap":private]=>array(2) {
        [0]=>int(5)
        [1]=>int(9)
    }
}

作为另一种可能性，我认为内存约束可能会导致堆损坏，但在这种情况下，让任何修改方法（insert, extract, ...）引发异常并将堆保持在原始状态似乎更有用.

所以我的问题是：为什么我们需要调用$heap->isCorrupted()，它会在哪种情况下返回true？

标签： phpheap

解决方案

compare当用户定义的函数中发生异常时，堆可能会损坏。SplHeap::compare上的文档有以下内容：

警告抛出异常SplHeap::compare()会破坏堆并将其置于阻塞状态。您可以通过调用取消阻止它SplHeap::recoverFromCorruption()。但是，某些元素可能未正确放置，因此可能会破坏堆属性。

例如，这个脚本会产生一个损坏的堆：

final class MySplHeap extends SplHeap {
    protected function compare($a, $b) {
        echo "compare $a with $b\n"; // Useful to see what is happening...
        if ($a === $b) return 0;
        if ($a > $b) return 1;
        throw new Exception("my error");
    }
}

$heap = new MySplHeap();

try {
    $heap->insert(3);
    $heap->insert(2);
    $heap->insert(1); 
    $heap->insert(4); // compare method raises error here
} catch(Exception $e) {}

var_dump($heap->isCorrupted()); // bool(true)

echo $heap->extract(); // RuntimeException: Heap is corrupted, heap properties are no longer ensured.

由于错误，无法将值 4 放置在堆中的正确位置。

显而易见的补救措施是确保比较函数中没有异常发生。

推荐阅读