The SplHeap class

(PHP 5 >= 5.3.0, PHP 7)

简介

The SplHeap class provides the main functionalities of a Heap.

类摘要

abstract SplHeap implements Iterator , Countable {

/* 方法 */

public __construct ( void )

abstract protected compare ( mixed $value1 , mixed $value2 ) : int

public count ( void ) : int

public current ( void ) : mixed

public extract ( void ) : mixed

public insert ( mixed $value ) : void

public isCorrupted ( void ) : bool

public isEmpty ( void ) : bool

public key ( void ) : mixed

public next ( void ) : void

public recoverFromCorruption ( void ) : void

public rewind ( void ) : void

public top ( void ) : mixed

public valid ( void ) : bool

}

SplHeap::compare — Compare elements in order to place them correctly in the heap while sifting up
SplHeap::__construct — Constructs a new empty heap
SplHeap::count — Counts the number of elements in the heap
SplHeap::current — Return current node pointed by the iterator
SplHeap::extract — Extracts a node from top of the heap and sift up
SplHeap::insert — Inserts an element in the heap by sifting it up
SplHeap::isCorrupted — Tells if the heap is in a corrupted state
SplHeap::isEmpty — Checks whether the heap is empty
SplHeap::key — Return current node index
SplHeap::next — Move to the next node
SplHeap::recoverFromCorruption — Recover from the corrupted state and allow further actions on the heap
SplHeap::rewind — Rewind iterator back to the start (no-op)
SplHeap::top — Peeks at the node from the top of the heap
SplHeap::valid — Check whether the heap contains more nodes

User Contributed Notes

Anthony 08-Jun-2016 12:15


If you wish to build a true tree based heap, you can do so as follows (implemented with SplMinHeap, but could be SplMaxHeap if you wish for the opposite order of items):



The stucture that we're trying to represent:



         1

         |

+-----+--+--+-----+

|     |     |     |

2     3     4     5

|     |           |

+   +-+-+         +

|   |   |         |

7   6   8         9

                  |

                +-+-+

                |   |

               10   11



<?php

$h = new SplMinHeap();



// [parent, child]

$h->insert([9, 11]);

$h->insert([0, 1]);

$h->insert([1, 2]);

$h->insert([1, 3]);

$h->insert([1, 4]);

$h->insert([1, 5]);

$h->insert([3, 6]);

$h->insert([2, 7]);

$h->insert([3, 8]);

$h->insert([5, 9]);

$h->insert([9, 10]);



for ($h->top(); $h->valid(); $h->next()) {

    list($parentId, $myId) = $h->current();

    echo "$myId ($parentId)\n";

}

?>



As you iterate over the heap, the return data will be read as if you're reading a book; ie left to right, top to bottom. It will NOT follow the relationships.



So, the above code will output the following:



1 (0)

2 (1)

3 (1)

4 (1)

5 (1)

7 (2)

6 (3)

8 (3)

9 (5)

10 (9)

11 (9)

igorsantos07 at gmail dot com 26-Jun-2014 01:02


While Michelangelo Van Dam example (http://br2.php.net/manual/en/class.splheap.php#93930) is a great demonstration of what can be done with SplHeap, this implementation is exactly what SplPriorityQueue does - based on SplMaxHeap. If you're planning to copy that snippet, go no further! There's a SPL class that does exactly what you want :)

Michelangelo van Dam 06-Oct-2009 11:44


To have a good idea what you can do with SplHeap, I created a little example script that will show the rankings of Belgian soccer teams in the Jupiler League.



<?php

/**

 * A class that extends SplHeap for showing rankings in the Belgian

 * soccer tournament JupilerLeague

 */

class JupilerLeague extends SplHeap 

{

    /**

     * We modify the abstract method compare so we can sort our

     * rankings using the values of a given array

     */

    public function compare($array1, $array2)

    {

        $values1 = array_values($array1);

        $values2 = array_values($array2);

        if ($values1[0] === $values2[0]) return 0;

        return $values1[0] < $values2[0] ? -1 : 1;

    }

}



// Let's populate our heap here (data of 2009)

$heap = new JupilerLeague();

$heap->insert(array ('AA Gent' => 15));

$heap->insert(array ('Anderlecht' => 20));

$heap->insert(array ('Cercle Brugge' => 11));

$heap->insert(array ('Charleroi' => 12));

$heap->insert(array ('Club Brugge' => 21));

$heap->insert(array ('G. Beerschot' => 15));

$heap->insert(array ('Kortrijk' => 10));

$heap->insert(array ('KV Mechelen' => 18));

$heap->insert(array ('Lokeren' => 10));

$heap->insert(array ('Moeskroen' => 7));

$heap->insert(array ('Racing Genk' => 11));

$heap->insert(array ('Roeselare' => 6));

$heap->insert(array ('Standard' => 20));

$heap->insert(array ('STVV' => 17));

$heap->insert(array ('Westerlo' => 10));

$heap->insert(array ('Zulte Waregem' => 15));



// For displaying the ranking we move up to the first node

$heap->top();



// Then we iterate through each node for displaying the result

while ($heap->valid()) {

  list ($team, $score) = each ($heap->current());

  echo $team . ': ' . $score . PHP_EOL;

  $heap->next();

}

?>



This results in the following output:

Club Brugge: 21

Anderlecht: 20

Standard: 20

KV Mechelen: 18

STVV: 17

Zulte Waregem: 15

AA Gent: 15

G. Beerschot: 15

Charleroi: 12

Racing Genk: 11

Cercle Brugge: 11

Kortrijk: 10

Lokeren: 10

Westerlo: 10

Moeskroen: 7

Roeselare: 6



Hope this example paved the way for more complex implementations of SplHeap.

The SplHeap class

简介

类摘要

Table of Contents

User Contributed Notes