堆

class Heap
{
    public $deep = 0;
    public $data = [];

    public function push($value)
    {
        $deepStartIndex = pow(2, $this->deep) - 1;
        $nextDeepStartIndex = $deepStartIndex + pow(2, $this->deep);
        array_push($this->data, $value);
        $lastIndex = array_key_last($this->data);
        if ($lastIndex == $nextDeepStartIndex) {
            $this->deep++;
        }
        $this->swapUp($lastIndex);
    }

    public function pop()
    {

        if (!isset($this->data[0])) {
            return null;
        }

        $min = $this->data[0];

        $lastIndex = array_key_last($this->data);
        $this->data[0] = $this->data[$lastIndex];
        unset($this->data[$lastIndex]);

        $deepStartIndex = pow(2, $this->deep) - 1;
        if ($deepStartIndex == 0) {
            return $min;
        }

        if ($lastIndex == $deepStartIndex) {
            $this->deep--;
        }

        $this->swapDown(0);

        return $min;
    }

    private function swapDown($index)
    {
        while (true) {
            $leftIndex = 2 * $index + 1;
            $rightIndex = 2 * $index + 2;

            $leftValue = !isset($this->data[$leftIndex]) ? $this->data[$index] + 1 : $this->data[$leftIndex];
            $rightValue = !isset($this->data[$rightIndex]) ? $this->data[$index] + 1 : $this->data[$rightIndex];

            if ($this->data[$index] <= $leftValue && $this->data[$index] <= $rightValue) {
                break;
            }

            $minIndex = $leftValue <= $rightValue ? $leftIndex : $rightIndex;

            $temp = $this->data[$index];
            $this->data[$index] = $this->data[$minIndex];
            $this->data[$minIndex] = $temp;
            $index = $minIndex;

        }
    }

    private function swapUp($index)
    {
        while (true) {

            if ($index == 0) {
                break;
            } else {
                if ($index % 2 == 0) {
                    $parentIndex = $index / 2 - 1;
                } else {
                    $parentIndex = floor($index / 2);
                }
            }

            if ($this->data[$parentIndex] > $this->data[$index]) {
                $temp = $this->data[$index];
                $this->data[$index] = $this->data[$parentIndex];
                $this->data[$parentIndex] = $temp;
                $index = $parentIndex;
            } else {
                break;
            }

        }
    }
}