My Blog
My Blog

The SplHeap class

SplHeap is a data structure. where an element is inserted directly in sorted positions  within certain conditions. SplHeap Implemented as a binary heap. every node has maximum of two child node. not possible to one leaf node have one or more leaves than others,it shape is balanced. either every child nodes greater than or equal or lesser than equal of it parents.

This is the abstract class you need to extend. the abstract method should implement with in your class. which is compare(), this function will compare $value1 and $value 2, if $value 1 is greater than $value2 its return positive number, its return 0 if its equal, its return -1 if $value2 is greater than $value1.  you can compare numbers, strings and etc

When compare method calling when inserting and deleting. something happened during the compare method and exception thrown, the SplHeap become unknown state. all heap write/ read method from that point on will throw RuntimeExeception saying heap is corrupted

Something happened during the compare method, SplHeap cannot guarantee that the heap is sorted in the way you have intended. but sometime its possible to recover regenerating or re adding element in heap. before you can do this you must unblock splheap in order for add elements, this done by recoverFromCorruption method . it does not do anything to recover from corruption. just release the flag and tells Splheap is corrupted (SPL_HEAP_CORRUPTED)

Below Example adds Belgium soccer  club and their rankings in to the heap, its automatically insert correct location of their ranking . it sort while insert

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();

foreach ($heap as $club) {
    list ($team, $score) = each ($club);
    echo $team . ': ' . $score . PHP_EOL;

}

 

 

Selection Sort

Selection sort i s another comparison based sorting algorithm. It similar to bubble sort but it will take fewer swapping than Bubble short  In Selection sort first we find minimum/ maximum value item of the array and place in to first place . If  sorting is ascending order we will take minimum value from the array  if sorting descending order we will take maximum value from the array.  In the second iteration we find second most minimum / maximum value from the array and place in to second place. This goes until we placed each numbers correctly sorted position.

 

As we Preceding image  We started with first item in the list which is 20. when we iterate the 1st loop.  we found the minimum value is 10  so we swapped place of 20  and vice versa. we have added minimum value. now we want to find second smallest value  from the array compared to second item which is 45 in right side now we able to see 20 is the smallest value than 45 now we swapped in to  2nd place , so it continue until the last elements

Now we implement the Selection Sort

function selectionSort($array)
{
    $len = count($array);

    for ($i = 0; $i < $len; $i++) {
        $min = $i;

        for ($j = $i + 1; $j < $len; $j++) {
            if ($array[$j] < $array[$min]) {
                $min = $j;
            }
        }


        if ($i != $min) {
            $tmp = $array[$i];
            $array[$i] = $array[$min];
            $array[$min] = $tmp;
        }
    }

    return $array;
}

You can see above it sorted ascending order if you want to descending order. simply you can change $array[$j] < $array[$min] to $array[$j] > $array[$min] and change $min to $max

Selection sort has two for loop with O to n but Selection Sort makes maximum n-1 number of swapping Selection sort best case , worst case and average case have similar complexity  O(n2)