输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
当大量数据排序后取前k个值，并且数据经常变化的时候堆排序非常有优势。
<?php
$heaparr = array();
function GetLeastNumbers_Solution($input, $k)
{
// write code here
global $heaparr;
$result = array();
$heaparr = array(0);
//构建完全二叉树
for($i = 1; $i<= count($input); $i++){
$heaparr[] = $input[$i-1];
}
//2.调整所有的子树使得符合最小堆的特性,从最后一个非叶子节点开始找就行，下标是sum/2
$max = count($input);
for ($idx = round($max /2); $idx >=1; $idx--) {
setNodeP($idx, $max);
}
//每次取走最上面的元素，然后把最大节点的元素放在顶部，重新调整，使得剩余的节点依旧满足最小堆的特性。
for($i = 1; $i<= $k; $i++){
$t = $heaparr[1];
$heaparr[1]=$heaparr[$max];
$max--;
setNodeP(1, $max);
$result[] = $t;
}
return $result;
}
function setNodeP($curIdx, $maxNode){
global $heaparr;
if($curIdx*2 > $maxNode) {
return;
}
$t = $curIdx;
if($heaparr[$curIdx]>$heaparr[$curIdx*2]){
$t = $curIdx * 2;
}
if($curIdx*2+1 <=$maxNode) {
if($heaparr[$t] > $heaparr[$curIdx*2+1]) {
$t = $curIdx * 2 + 1;
}
}
if($t!=$curIdx) {
$tem = $heaparr[$curIdx];
$heaparr[$curIdx] = $heaparr[$t];
$heaparr[$t] = $tem;
setNodeP($t, $maxNode);
}
}
$result = GetLeastNumbers_Solution(array(3,2,1,0,-1),3);
print_r($result);
?>
