堆的定義：

n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）：(1) ki<=k(2i) 且 ki<=k(2i+1)(1≤i≤n/2），當然，這是小根堆，大根堆則換成>=號。k(i）相當于二叉樹的非葉子結點，K(2i）則是左子節(jié)點，k(2i+1）是右子節(jié)點。若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹：樹中任一非葉子結點的關鍵字均不大于（或不小于）其左右孩子（若存在）結點的關鍵字。

/** * 調整堆 * @param array $arr	排序數(shù)組 * @param int $i    	待調節(jié)元素的下標 * @param int $size 	數(shù)組大小, 準確來說是數(shù)組最大索引值加1 */function heapAjust(& $arr, $i, $size){	$key = $arr[$i];	// 索引從0開始	// 左孩子節(jié)點為 2i+1, 右孩子節(jié)點為 2i+2	for($j = 2 * $i + 1; $j < $size; $j = 2 * $j + 1) {		if($j + 1 < $size && $arr[$j] < $arr[$j + 1])			$j++;		if($key > $arr[$j])			break ;		$arr[$i] = $arr[$j]; //調換值		$i = $j;	}	$arr[$i] = $key;}/** * 堆排序 * 時間復雜度：O(nlogn) * 不穩(wěn)定的排序算法 */function heapSort(& $arr){	$len = count($arr);		// 構建初始大根堆	for($i = intval($len/2); $i >= 0; $i--) {		heapAjust($arr, $i, $len);	}	// 調換堆頂元素和最后一個元素	for($j = $len - 1; $j > 0; $j--) {		$swap = $arr[0];		$arr[0] = $arr[$j];		$arr[$j] = $swap;		heapAjust($arr, 0, $j); //繼續(xù)調整剩余元素為大根堆	}}