Incorrect Result Order with PHP Heaps

Question

I'm running in to an issue where none of the PHP heap classes store the data in the correct order.

Examples given are trivial, but the error with this small dataset makes a project I'm working on fail spectacularly.

Simple Example:

$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>";

Expected Output:

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
        )

)

Actual Output:

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
        )

)

You can change the order of the initial values array to [9,8,7,6,5,4,3,2,1] and max heap shows correctly, but min heap is out of order. Both are out of order if the values are randomized [1,9,2,8,3,7,4,6,5] shows

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
        )

)

I've tried the exact code with different $values arrays on https://onlinephp.io/ against different PHP versions, and each one I've tested returns the results the same way, so I have to be misunderstanding the functionality of the heaps (and SplPriorityQueue as it uses max heap but also stores the additional data to process like a queue.

Answer 1

You seem to think that the array representation of a heap must be sorted. This is not true. A heap only guarantees order between child and parent. In a min-heap a child's value is never less than its parent's value, and in a max-heap it is never greater. See also the definition on Wikipedia.

Let's look at the last of your examples where you claim they are "out of order":

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

This array is the representation of this binary tree:

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

As we can see, the min-heap property is nowhere violated: every child node has a value that is not less than its parent has. So it is a valid min-heap.

And the max heap:

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

This array represents this binary tree:

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

Also here we can see that the max-heap property is nowhere violated: every child node has a value that is not greater than its parent has. So it is a valid max-heap.