二叉堆binary heap(2)小根堆を利用して最大top kを求める

操作を迅速に実行する性質は、スタック順序性である.最小要素を迅速に見つけたいので、最小要素は根元にあるはずです.
同様に、maxスタックを宣言し、最大メタを見つけて削除することができます.
1つのスタックでは、各ノードXについて、Xのparentのキーワード<=Xのキーワードは、ルートノードを除く(parentはない).
* Heap/BinMinHeap.php

elements = new \SplFixedArray($maxElements + 1);
        $this->capacity = $maxElements;
        $this->size = 0;
        /* dumb position 0 */
        $this->elements[0] = self::MIN_DATA;

        $this->comparator = $cmp;
    }

    public function isFull() {
        return $this->size >= $this->capacity;
    }

    public function insert($x) {
        if ($this->isFull()) {
            throw new \RuntimeException("Priority queue is full");
        }
        for ($i = ++$this->size; $this->elements[$i>>1] > $x; $i >>= 1) {
            $this->elements[$i] = $this->elements[ $i>>1 ];
        }
        $this->elements[ $i ] = $x;
    }

    public function isEmpty() {
        return $this->size === 0;
    }

    public function deleteMin() {
        if ($this->isEmpty()) {
            return $this->elements[0];
        }
        $minElement = $this->elements[1];
        $lastElement = $this->elements[$this->size--];

        for ($i = 1; $i * 2 <= $this->size; $i = $child) {
            /* find smaller child */
            $child = $i * 2;
            if ($child !== $this->size &&
                $this->comparator->lessThan(
                    $this->elements[$child+1], $this->elements[$child])) {
                $child++;
            }
            /* Percolate one level */
            if ($this->comparator->greeterThan($lastElement, $this->elements[$child])) {
                $this->elements[$i] = $this->elements[$child];
            } else {
                break;
            }
        }
        $this->elements[$i] = $lastElement;
        return $minElement;
    }

    public function findMin() {
        return $this->isEmpty() ? $this->elements[0] : $this->elements[1];
    }

    public function __destruct() {
        for ($i = $this->size-1; $i >= 0; $i--) {
            unset($this->elements[$i]);
        }
        $this->elements = null;
    }
    public function makeEmpty() {
        $this->size = 0;
    }

    public function getComparator() {
        return $this->comparator;
    }

    public function __toString() {
        if (0 === $this->size) {
            $s = "[]";
        } else {
            $s = '[';
            for ($i = 1, $last = $this->size+1; $i < $last; $i++) {
                $s .= json_encode($this->elements[$i]).',';
            }
            $s[strlen($s)-1] = ']';
        }
        return sprintf("{capacity: %d, size: %d, elements: %s}", $this->capacity, $this->size, $s);
    }

    public function getElements() {
        $e = [];
        for ($i = 1, $last = $this->size+1; $i < $last; $i++) {
            $e[] = $this->elements[$i];
        }
        return $e;
    }
}

* Heap/TopK.php

 count($a)) {
            throw new \LengthException('k < 1 or > count($a)');
        }
        if (is_null($cmp)) {
            $cmp = new Comparator();
        }
        $heap = new BinMinHeap($k, $cmp);
        while ( ! $heap->isFull() ) {
            $heap->insert(current($a));
        }
        while ( ($c = current($a)) !== false ) {
            if ( ! $heap->getComparator()->lessThan($c, $heap->findMin()) ) {
                $heap->deleteMin();
                $heap->insert($c);
            }
            next($a);
        }
        $this->heap = $heap;
    }

    public function insert($x) {
        if (! $this->heap->getComparator()->lessThan($x, $this->heap->findMin()) ) {
            $this->heap->deleteMin();
            $this->heap->insert($x);
        }
    }

    public function bulkInsert(array $a) {
        foreach ($a as $v) {
            $this->insert($v);
        }
    }

    public function getElements() {
        return $this->heap->getElements();
    }

    public function __toString() {
        return $this->heap->__toString();
    }
}

* util/Comparator.php

compare = function($a, $b) {
                if ($a === $b) {return 0;}
                return $a > $b ? 1 : -1;
            };
            return;
        }
        $this->compare = $compareFunction;
    }
    /*** @return bool */
    public function equal($a, $b) {
        return call_user_func($this->compare, $a, $b) === 0;
    }

    /*** @return bool */
    public function lessThan($a, $b) {
        return call_user_func($this->compare, $a, $b) < 0;
    }

    /*** @return bool */
    public function greeterThan($a, $b) {
        return call_user_func($this->compare, $a, $b) > 0;
    }

    /*** @return bool */
    public function lessThanOrEqual($a, $b) {
        return $this->lessThan($a, $b) || $this->equal($a, $b);
    }

    /*** @return bool */
    public function greeterThanOrEqual($a, $b) {
        return $this->greeterThan($a, $b) || $this->equal($a, $b);
    }

    public function reverse() {
        $compareOriginal = $this->compare;
        $this->compare = function ($a, $b) use ($compareOriginal) {
            return $compareOriginal($b, $a);
        };
    }
}

* autoload.php

* index.php

 'c', 'freq'=> 12],
    ['char'=> 'e', 'freq'=> 16],
    ['char'=> 'b', 'freq'=>9],
    ['char'=> 'd', 'freq'=> 13],
    ['char'=> 'a', 'freq'=>5],
    ['char'=> 'f', 'freq'=> 45]
];
$b = new TopK($a, 2, new Comparator(
        function($a, $b) {return $a['freq'] - $b['freq'];}
    ));
echo json_encode($b->getElements()).PHP_EOL;

$b->bulkInsert([
    ['char' => 'g', 'freq' => 50],
    ['char' => 'h', 'freq' => 40],
]);
echo json_encode($b->getElements()).PHP_EOL;
echo $b.PHP_EOL;
unset($a, $b);

//       ASCII   3   
$s = "The SplPriorityQueue class";
$s = preg_replace('/\s+/', '', $s);
for ($i = 0, $n = strlen($s); $i < $n; $i++) {
    $s[$i] = chr( ord($s[$i]) & 0xdf );
}
echo $s.PHP_EOL; // THESPLPRIORITYQUEUECLASS
$a = str_split($s);
$b = new TopK($a, 3, new Comparator(function($a, $b) {
    return strcmp($a, $b);
}));

// ACEEEHIILLOPPQRRSSSTTUUY
echo implode('', $b->getElements()).PHP_EOL;  // UYU

* test
$ php index.php 
[{"char":"e","freq":16},{"char":"f","freq":45}]
[{"char":"f","freq":45},{"char":"g","freq":50}]
{capacity: 2, size: 2, elements: [{"char":"f","freq":45},{"char":"g","freq":50}]}
THESPLPRIORITYQUEUECLASS
UYU