A binary heap class

    (Available since version 1.0)

    Introduction

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

    It provides the same interface as SplHeap with the extra methods, Heap::extractInsert() and 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::Binary::MaxHeap and SEIDS::Heaps::Binary::MinHeap for a binary max-heap and binary min-heap respectively.

    Class synopsis

    SEIDS::Heaps::Binary::Heap extends SEIDS::Heaps::Heap {
    /* Properties */
    protected array $btree ;
    protected array $hasht ;
    protected int $last_tag ;
    /* Inherited properties */
    protected int $size ;
    /* Methods */
    public __construct ([ array $array ] )
    abstract protected int compare ( mixed $value1 , mixed $value2 )
    public mixed extract ( void )
    public mixed extractInsert ( mixed $value )
    public bool insert ( mixed $value )
    public bool recoverFromCorruption ( void )
    public mixed top ( void )
    public void update ( mixed $value1 , mixed $value2 )
    protected int parentIndex ( int $index )
    protected int childOneIndex ( int $index )
    protected int childTwoIndex ( int $index )
    protected void swap ( int $a , int $b )
    protected void siftDown ( int $index )
    protected void siftUp ( int $index )
    /* 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

    btree

    The binary tree which represents 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 indexes (in btree) 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