7. Data structure (PHP implementation) — the underlying implementation of the priority queue (heap)

1. Description:

• Is based on a binary tree to achieve

Time complexity

3. The floating operation of the insert node (in order to put the maximum at the top) (in the code siftUp method)

4. Drop the minimum value after popping the maximum node (in the code siftDown method)

5. The code

<? PHP /** * Content: namespace heapBundle * auth: creat: 2020-11-09 */ namespace heapBundle; use ArrayBundle\BaseArray; Class TreeHeap {/** * data * @var BaseArray */ protected $data; public function setData(BaseArray $baseArray): self { $this->data = $baseArray; return $this; } public function __construct() { $this->data = new BaseArray(); Public function getSize(): int {return $this->data->getSize();} return $this->data->getSize(); } /** * @param int $index * @return int * @throws Exception */ public function parentIndex(int $index): Int {if ($index <= 0) {throw new \Exception(' Index must be > 0! '); } return ($index - 1) / 2; } public function leftChildinIndex (int $index);} public function leftChildinIndex (int $index); int { return $index * 2 + 1; } public function rightChildinIndex (int $index);} public function rightChildinIndex (int $index); int { return $index * 2 + 2; } / get the most value * * * * @ return string | int | null * / public function getMaxValue () {return $this - > data - > getSize () > 0? $this->data->getFirst() : null; Popup heap} / * * * * @ the largest element in the return int | string * @ throws \ | null Exception * / public function popMaxValue () {/ / if there is no heap, $this->getMaxValue(); $this->getMaxValue(); if (is_null($maxValue)) return null; $this->data->swap(0, $this->data->getSize() - 1); $this->data->del($this->data->getSize() - 1); $this->siftDown(0); return $maxValue; } /** * add data * @param $value * @throws Exception */ public function add($value) {// Add ($value) $this->data->addLast($value); $this->siftUp($this->data->getSize() -1); $this->data->getSize() -1); } /** * float operation, * @Param int $index * @Exception */ protected function siftUp(int $index) {// If the index is greater than 0 and the index is greater than 0 The value of the parent is smaller than the value of the current node, $this->data->get($this->parentIndex($index)); $this->parentIndex($index); $this-> data-bb3 swap($index, $this->parentIndex($index)); $this-> data-bb3 swap($index, $this->parentIndex($index)); $index = $this->parentIndex($index); $index = $this->parentIndex($index); }} /** * sink operation, * @param int $index * @throws Exception */ protected function siftDown(int $index) {while $this-> leftChildinIndex ($index) < $this->data->getSize()) {$this-> leftChildinIndex ($index) = $this->data->getSize(); // Compare the values of left and right children, If (($this->data->get($this-> rightChildinIndex ($index)), $this-> rightChildinIndex ($index)), $this-> rightChildinIndex ($index)), $this->data->get($childIndex)) > 0) { $childIndex = $this->rightChildIndex($index); } if (bccomp($this->data->get($index), $this->data->get($childIndex)) >= 0) {break; $this->data->swap($index, $childIndex); $this->data->swap($index, $childIndex); $index = $childIndex; $index = $childIndex; }} /** * ReplacemaxValue ($newValue) * @param $newValue * @return bool * @throws \Exception */ public function replacemaxValue ($newValue):  bool { $maxValue = $this->getMaxValue(); if (is_null($maxValue)) return false; $this->data->set(0, $newValue); $this->siftDown(0); return true; } /** * @throws () {for ($I = $this->data->getSize() - 1; $i >= 0; $i--) { $this->siftDown($i); Public function varDump(): void {echo (string)$this-> data.php_eol; }}

6. Sample

<? php require_once __DIR__ . '/.. /.. /vendor/autoload.php'; $heap = new HeapBundleTreeHeap(); 1 for ($i = 0; $i < 10; $i++) { $heap->add($i); } for ($i = 0; $i < 10; $i++) { var_dump($heap->popMaxValue()); }

int(9)
int(8)
int(7)
int(6)
int(5)
int(4)
int(3)
int(2)
int(1)
int(0)