牛客NC357 矩阵第K小【中等 堆 Java、Go、PHP】-参考答案PHP

<?php


/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param matrix int整型二维数组 
 * @param k int整型 
 * @return int整型
 */
function KthinMatrix( $matrix ,  $k )
{
    // 堆，优先级队列
    $pq = new PQ();
    $n =count($matrix);
    $visited = [];
    for($i=0;$i<$n;$i++){
        for($j=0;$j<$n;$j++){
            $visited[$i][$j] =false;
        }
    }

    $pq->add(0,0,$matrix[0][0]);
    $visited[0][0]= true;

    for($i=0;$i<$k-1;$i++){
        $poll = $pq->poll();
        $x = $poll[0];
        $y = $poll[1];

        if($x <$n && $y+1<$n && !$visited[$x][$y+1]){
            $pq->add($x,$y+1,$matrix[$x][$y+1]);
            $visited[$x][$y+1]=true;
        }

        if($x+1<$n&&$y<$n && !$visited[$x+1][$y]){
            $pq->add($x+1,$y,$matrix[$x+1][$y]);
            $visited[$x+1][$y]=true;
        }
    }

    return $pq->poll()[2];
}


//本答案用对，小顶对，也就是从上往下是递增的
class PQ{
    public $arr=[]; //二维数组，0：横坐标 1：纵坐标  2：坐标值
    public $defaultsize =10;
    public $size;
    public function __construct()
    {
        $this->size =0;
        for($i=0;$i<$this->defaultsize;$i++){
            $this->arr[$i] =[];
        }
    }


    public function ensurecap($cap){
        $curlen =count($this->arr);
        if($curlen >= $cap){
            return;
        }

        $newlen = $curlen+$curlen>>1;
        $newarr = [];
        for($i=0;$i<$newlen;$i++){
            if($i<$curlen){
                $newarr[$i] = $this->arr[$i];
            }else{
                $newarr[$i] =[];
            }
        }
        $this->arr = $newarr;
    }

    public function  add($x,$y,$data){
        $this->ensurecap($this->size+1);
        $this->arr[$this->size] = [$x,$y,$data];
        $this->shiftup($this->size);
        $this->size++;
    }


    //上滤
    public function shiftup($idx){
        $root = $this->arr[$idx];
        while ($idx>0){
            $pidx = ($idx-1) >>1;
            $parent= $this->arr[$pidx];

            if($parent[2] <=$root[2]){ //当前节点比父节点大，退出
                break;
            }

            $this->arr[$idx] = $parent;
            $idx = $pidx;
        }
        $this->arr[$idx] = $root;
    }

    public function poll() {
        $root = $this->arr[0];
        $this->arr[0] = $this->arr[$this->size-1];
        $this->size-=1;
        $this->shiftdown(0);
        return $root;
    }

    //下窜
    public function shiftdown($idx){
        $root = $this->arr[$idx];
        $half = $this->size >>1;
        while ($idx<$half){
            $childidx = ($idx << 1)+1;
            $rightidx = $childidx+1;
            $child = $this->arr[$childidx];

            if($rightidx<$this->size && $child[2] > $this->arr[$rightidx][2]){
                $childidx = $rightidx;
                $child = $this->arr[$rightidx];
            }

            if($child[2] >=$root[2]){
                break;
            }

            $this->arr[$idx] = $child;
            $idx =$childidx;
        }
        $this->arr[$idx] = $root;
    }
}