php head topN算法

原文https://diffnest.github.io/2019/07/01/PHP小顶堆实现TopK/
<?php
class Topk
{
    public $top;
    public $topkArr = array();
    public $topkList = array();
    
    public function __construct($topk) {
        $this->top = $topk;
    }

    public function swap(&$arr, $i, $j) 
    {
        $temp = $arr[$i];
        $arr[$i] = $arr[$j];
        $arr[$j] = $temp;
    }
    //n：节点
    //i: 从哪个节点heapify
    private function heapify(&$tree, $n, $i)
    {
        if ($i >= $n) {
            return; 
        }

        $c1 = (2 * $i) + 1;//左节点
        $c2 = (2 * $i) + 2;//右节点
        $max = $i;
   
        //左右节点内容跟父节点比较，确保父节点是最大值
        if ($c1 < $n && $tree[$c1] > $tree[$max]) {
            $max = $c1;
        }
        if ($c2 < $n && $tree[$c2] > $tree[$max]) {
            $max = $c2;
        }
        //当i是最大值时，不用交换
        if ($max != $i) {
            $this->swap($tree, $max, $i);
            //交换之后对下一层继续heapify
            $this->heapify($tree, $n, $max);
        }
    }

    //从下往上构建堆：节点3->节点2->节点1
    public function buildHeap(&$tree, $n) 
    {
        $lastNode = $n - 1;
        $parent = ($lastNode - 1) / 2;
        for ($i = $parent; $i >= 0; $i--) {
            $this->heapify($tree, $n, $i);
        }
    }

    public function heapSort(&$tree, $n)
    {
        $this->buildHeap($tree, $n);
        for($i = $n-1; $i >= 0; $i--) {
            $this->swap($tree, $i, 0);
            //剩下的i个元素重新构建成堆
            $this->heapify($tree, $i, 0);
        }
    }

    //调整
    public function adjust($value)
    {   
        if (in_array($value, $this->topkArr)) {
            return;
        }

        //记录原始数据
        $this->init($value);
        $len = count($this->topkList);

        if ($len < $this->top) {
            array_push($this->topkList, $value);
            $this->heapSort($this->topkList, $len);
        } else {
            //堆顶值与新值比较
            if ($this->topkList[0] < $value) {
                if (count($this->topkList) >= $this->top) {
                    $this->topkList[0] = $value;
                } else {
                    array_unshift($this->topkList, $value);
                }
                $this->heapSort($this->topkList, $len);
            }
        }
    }

    public function getTopK()
    {
        return $this->topkList;
    }

    public function init($value)
    {
        array_push($this->topkArr, $value);
    }

    public function getInitData()
    {
        return $this->topkArr;
    }

    public function calc()
    {
        for ($i = 0; $i < 10; $i++) {
            $this->adjust(mt_rand(1, 100));
        }
    }
}
$heapTree = new Topk(5);
$heapTree->calc();
echo '<pre>';
var_dump($heapTree->getInitData(), $heapTree->getTopK());



?>