A pairing min-heap class

(Available since version 1.0)

Introduction

This class provides the main functionalities of a heap, keeping the minimum on the top. The underlying implementation is a pairing heap.

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

SEIDS::Heaps::Pairing::MinHeap extends SEIDS::Heaps::Pairing::Heap {

/* Inherited properties */

protected int $size ;

protected SEIDS::Heaps::Pairing::Subheap $subheap ;

protected array $hasht ;

protected int $last_tag ;

/* Methods */

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

/* Inherited methods */

public Heap::__construct ([ array $array ] )

public int Heap::count ( void )

public mixed Heap::current ( void )

public bool Heap::isEmpty ( void )

public int Heap::key ( void )

public void Heap::next ( void )

public void Heap::rewind ( void )

public bool Heap::valid ( void )

protected mixed Heap::value ( mixed $value )

protected mixed Heap::hashtIndex ( mixed $value )

public void Heap::__clone ( void )

public mixed Heap::extract ( void )

public bool Heap::insert ( mixed $value )

public bool Heap::recoverFromCorruption ( void )

public mixed Heap::top ( void )

public void Heap::update ( mixed $value1 , mixed $value2 )

protected SEIDS::Heaps::Pairing::Subheap Heap::merge ( SEIDS::Heaps::Pairing::Subheap $a , SEIDS::Heaps::Pairing::Subheap $b )

protected void Heap::mergePairs ( SubHeap $subheap )

protected void Heap::swapWithParent ( SubHeap $child )

protected void Heap::siftDown ( SubHeap $subheap )

protected void Heap::siftUp ( SubHeap $subheap )

}