Home > Sort algorithms > Heapsort algorithm – PHP implementation

Heapsort algorithm – PHP implementation

Heapsort is a comparison-based sorting algorithm to create a sorted array (or list), and is part of the selection sort family.
Algorithm:

  1. Build a heap (heap is a tree structure with rule that parent value are bigger or equal with childrens values) out of the data.
  2. Removing the largest element from the heap and insert in sorted array starting with first position (0).
  3. Reconstruct the heap with remaining elements and add largest value in sorted array.

Heap sort can be performed in place by spliting the array in two parts, the heap and the sorted array.
Performance:

  • Worst case: O(n logn)
  • Average case: O(n logn)
  • Best case: O(n logn)

PHP implementation (a special class for heap sorting):

 
class heapSort {
    /**Change first value to the end of array recursively
     * 
     * @param array $array
     * @return array
     */
    public function heap(&$array) {
        $length=count($array);
        $this->heapify($array,$length);
        $end=$length-1;
        while ($end>0) {
            $tmp=$array[0];
            $array[0]=$array[$end];
            $array[$end]=$tmp;
            $end=$end-1;
            $this->siftDown($array,0,$end);
        }
        return $array;
    }
    /**Build binary tree 
     * 
     * @param array $array
     * @param integer $count
     */
    private function heapify(&$array,$count) {
        $start=floor(($count-2)/2);
        while ($start>=0) {
            $this->siftDown($array,$start,$count-1);
            $start=$start-1;
        }
    }
    /**Arrange tree branch: parent node bigger than his children
     * 
     * @param array $array
     * @param integer $start
     * @param integer $end
     * @return when tree is sorted
     */
    private function siftDown(&$array,$start,$end) {
        $root=$start;
        while ($root*2+1<=$end) {
            $left=$root*2+1;
            $swap=$root;
            //check who is the bigger between root,left child and right child
            if ($array[$swap]<$array[$left]){
                $swap=$left;
            } 
            if ($left+1<=$end && $array[$swap]<$array[$left+1]){
                $swap=$left+1;
            }
            //swap root with bigger children (if exist)
            if ($swap!=$root) {
                $tmp=$array[$root];
                $array[$root]=$array[$swap];
                $array[$swap]=$tmp;
                $root=$swap;
            } else return;
        }
    }
}

Bibliography:

  1. Introduction to Algorithms – Thomas H.Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
  2. Algorithms – Robert Sedgewick
  3. http://en.wikipedia.org/wiki/Heapsort
Advertisements
Categories: Sort algorithms Tags: , ,
  1. No comments yet.
  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: