Difference between revisions of "Heap & Heap Sort"

Latest revision as of 22:58, 14 January 2013

Heap & Heap Sort

<?php
//Heap sort
function swap(&$a,&$b){
	$a=$b+$a-($b=$a);
}
function insert(&$arr,$val){
	$len=sizeof($arr);
	array_push($arr,$val);
	siftUp($arr,$len);
}
function siftUp(&$arr,$pos){
	$parent=floor(($pos-1)/2);
	if($parent>=0){
		if($arr[$parent]<$arr[$pos]){//find child is larger then swap
			swap($arr[$parent],$arr[$pos]);
		}
		if($parent>0){
			siftUp($arr,$parent);//sift up again
		}
	}
}
function levelPrint($arr){
	$depth=depth(sizeof($arr)-1);
	$len=pow(2,$depth);
	$lastLevel=0;
	$currentLevel=0;
	for($i=0;$i<sizeof($arr);$i++){
		$currentLevel=depth($i);
		if($currentLevel!=$lastLevel){
			$lastLevel=$currentLevel; 
			echo "<br />";
		}
		for ($j=0;$j<floor($len/($currentLevel+1));$j++){
			echo " ";
		}
		echo $arr[$i];
		
	}
}
function depth($n){//from 0 to ----
	$p=floor(($n-1)/2);
	if($p<0)
	return 0;
	else if($p==0)
	return 1;
	else
		return depth($p)+1;
}
function maxHeapSort($arr){
	$len=sizeof($arr);
	$i=$len-1;
	while($i>0){
		siftUp($arr,$i);
		$i--;
	}
	return $arr;
}
$a=array(0,8,3,5,1,9,4,7,2,6);
$b=array(7,9,6,2,8,1,4,0,5,3);
//$b=maxHeapSort($a);
$insertarr=array();
foreach($a as $v){
insert($insertarr,$v);
}
echo "Insert Res: <br/>";
levelPrint($insertarr);
var_dump($insertarr);
echo "heapSort Res: <br/>";
$sorted=maxHeapSort($b);
levelPrint($sorted);

Output:

Insert Res: 
        9
    7    8
  5  6  3  4
  0  2  1
array
  0 => int 9
  1 => int 7
  2 => int 8
  3 => int 5
  4 => int 6
  5 => int 3
  6 => int 4
  7 => int 0
  8 => int 2
  9 => int 1
heapSort Res: 
        9
    8    6
  5  7  1  4
  0  2  3

Other references
http://www.cprogramming.com/tutorial/computersciencetheory/heapcode.html