最小的K个数

输入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);
?>