<?php 
/**
 * 堆排序
 */


function heapSort($arr){
	$len = count($arr);
	initHeap($arr);//初始化堆
	for($end=$len-1;$end>0;$end--){//交换堆顶和最后的一个元素
		$tmp = $arr[$end];
		$arr[$end] = $arr[0];
		$arr[0] = $tmp;
		
		//调整堆，堆顶元素破坏了堆结构
		adjustHeap($arr,0,$end-1);//$end-1
	}
	return $arr;
}

function initHeap(&$arr){
	$len = count($arr);
	//最后一个非叶子节点开始，到根节点
	for($start=floor($len/2)-1;$start>=0;$start--){
		adjustHeap($arr,$start,$len-1);
	}
}

/*
 * $arr 待调整数组
 * $start 待调整节点的下标（区别于在二叉树中编号，-1）
 * $end 结束下标
 */
function adjustHeap(&$arr,$start,$end){
	$max = $start;
	$lchild_index = 2*($start+1)-1;
	$rchild_index = 2*($start+1);
	
	if($lchild_index<=$end){
		if($arr[$lchild_index]>$arr[$max]){
			$max = $lchild_index;
		}
		
		if($rchild_index<=$end&&$arr[$rchild_index]>$arr[$max]){
			$max = $rchild_index;
		}
		
		
	}
	
	if($max !=$start){
		$tmp = $arr[$start];
		$arr[$start] = $arr[$max];
		$arr[$max] = $tmp;
		
		adjustHeap($arr, $max, $end);
 	}
}

$arr = array(2,4,5,2,4,6,3,1,2,7,8);
echo count($arr);
print_r(heapSort($arr));
?>