Difference between revisions of "Heap & Heap Sort"

From Hawk Wiki
Jump to: navigation, search
(Created page with "==Heap & Heap Sort== <pre> <?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,$l...")
 
(Heap & Heap Sort)
 
(3 intermediate revisions by the same user not shown)
Line 1: Line 1:
 
==Heap & Heap Sort==
 
==Heap & Heap Sort==
<pre>
+
<pre class="php">
 
<?php
 
<?php
 
//Heap sort
 
//Heap sort
Line 72: Line 72:
 
levelPrint($sorted);
 
levelPrint($sorted);
 
</pre>
 
</pre>
 +
Output:
 +
<pre class="none">
 +
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
 +
</pre>
 +
 +
Other references <br>
 +
http://www.cprogramming.com/tutorial/computersciencetheory/heapcode.html

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