A pairing heap class

    (Available since version 1.0)

    Introduction

    This class provides the main functionalities of a Heap. The underlying implementation is a pairing heap.

    It provides the same interface as SplHeap with the extra method, Heap::update() which allows one to update a node in the heap.

    This class has just one abstract method, Heap::compare(), that must by overloaded to use the heap. Those who are working with simple numerical data can used the concrete classes SEIDS::Heaps::Pairing::MaxHeap and SEIDS::Heaps::Pairing::MinHeap for a pairing max-heap and pairing min-heap respectively.

    Class synopsis

    SEIDS::Heaps::Pairing::Heap extends SEIDS::Heaps::Heap {
    /* Properties */
    protected SEIDS::Heaps::Pairing::Subheap $subheap ;
    protected array $hasht ;
    protected int $last_tag ;
    /* Inherited properties */
    protected int $size ;
    /* Methods */
    public __construct ([ array $array ] )
    public void __clone ( void )
    abstract protected int compare ( mixed $value1 , mixed $value2 )
    public mixed extract ( void )
    public bool insert ( mixed $value )
    public bool recoverFromCorruption ( void )
    public mixed top ( void )
    public void update ( mixed $value1 , mixed $value2 )
    protected SEIDS::Heaps::Pairing::Subheap merge ( SEIDS::Heaps::Pairing::Subheap $a , SEIDS::Heaps::Pairing::Subheap $b )
    protected void mergePairs ( SubHeap $subheap )
    protected void swapWithParent ( SubHeap $child )
    protected void siftDown ( SubHeap $subheap )
    protected void siftUp ( SubHeap $subheap )
    /* Inherited methods */
    public int count ( void )
    public mixed current ( void )
    public bool isEmpty ( void )
    public int key ( void )
    public void next ( void )
    public void rewind ( void )
    public bool valid ( void )
    protected mixed value ( mixed $value )
    protected mixed hashtIndex ( mixed $value )
    }

    Properties

    subheap

    The top node of the heap.

    hasht

    A hash table (standard PHP array) which takes node values (as given by Heap::hashtIndex()) as keys and gives a list of nodes (represented as SubHeap objects) and tags for nodes corresponding to that value. Used to efficiently update the heap.

    last_tag

    The last tag used for a node.

    See Also

    Table of Contents

    To Top