PHP 堆的结果顺序不正确

Question

我遇到了一个问题，没有一个 PHP 堆类以正确的顺序存储数据。

给出的示例很简单，但是这个小数据集的错误使我正在处理的项目惨败。

简单示例：

$values = [1,2,3,4,5,6,7,8,9];
$min = new SplMinHeap();
$max = new SplMaxHeap();
foreach($values as $value){
  $min->insert($value);
  $max->insert($value);
}

echo "<pre>";
print_r($min);
print_r($max);
echo "</pre>";

预期输出：

SplMinHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
            [3] => 4
            [4] => 5
            [5] => 6
            [6] => 7
            [7] => 8
            [8] => 9
        )

)
SplMaxHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 9
            [1] => 8
            [2] => 7
            [3] => 6
            [4] => 5
            [5] => 4
            [6] => 3
            [7] => 2
            [8] => 1
        )

)

实际产量：

SplMinHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 1
            [1] => 2
            [2] => 3
            [3] => 4
            [4] => 5
            [5] => 6
            [6] => 7
            [7] => 8
            [8] => 9
        )

)
SplMaxHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 9
            [1] => 8
            [2] => 6
            [3] => 7
            [4] => 3
            [5] => 2
            [6] => 5
            [7] => 1
            [8] => 4
        )

)

您可以将初始值数组的顺序更改为 [9,8,7,6,5,4,3,2,1]，最大堆显示正确，但最小堆显示乱序。如果值是随机的，则两者都是乱序的 [1,9,2,8,3,7,4,6,5] 显示

SplMinHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 1
            [1] => 3
            [2] => 2
            [3] => 5
            [4] => 8
            [5] => 7
            [6] => 4
            [7] => 9
            [8] => 6
        )

)
SplMaxHeap Object
(
    [flags:SplHeap:private] => 0
    [isCorrupted:SplHeap:private] => 
    [heap:SplHeap:private] => Array
        (
            [0] => 9
            [1] => 8
            [2] => 7
            [3] => 6
            [4] => 3
            [5] => 2
            [6] => 4
            [7] => 1
            [8] => 5
        )

)

我已经在 https://onlinephp.io/ 上针对不同的 PHP 版本尝试了使用不同 $values 数组的确切代码，并且我测试过的每个代码都以相同的方式返回结果，所以我必须误解堆的功能（以及 SplPriorityQueue，因为它使用最大堆，但也像队列一样存储要处理的附加数据。

Answer 1

您似乎认为堆的数组表示必须是“已排序”的。这不是真的。堆仅保证子级和父级之间的顺序。在最小堆中，子级的值永远不会小于其父级的值，而在最大堆中，它永远不会大于。另请参阅维基百科上的定义。 让我们看一下您声称它们“乱序”的最后一个示例：

    [heap:SplHeap:private] => Array
        (
            [0] => 1
            [1] => 3
            [2] => 2
            [3] => 5
            [4] => 8
            [5] => 7
            [6] => 4
            [7] => 9
            [8] => 6
        )

这个数组就是这个二叉树的表示：

        1
      /   \
     3     2
    / \   / \
   5   8 7   4
  / \
 9   6

正如我们所看到的，最小堆属性没有被违反：每个子节点的值不小于其父节点的值。所以它是一个有效的最小堆。

最大堆：

    [heap:SplHeap:private] => Array
        (
            [0] => 9
            [1] => 8
            [2] => 7
            [3] => 6
            [4] => 3
            [5] => 2
            [6] => 4
            [7] => 1
            [8] => 5
        )

这个数组代表这个二叉树：

        9
      /   \
     8     7
    / \   / \
   6   3 2   4
  / \
 1   5

在这里我们还可以看到 max-heap 属性没有被违反：每个子节点的值都不大于其父节点的值。所以它是一个有效的最大堆。