Heap is a common data structure. The bottom layer is a binary tree implemented with an array. But there is no parent or child pointer. Sort by heap properties. There are minimum heaps and maximum heaps.

  • Minimum heap: The value of the parent node is smaller than the value of each child node
  • Maximum heap: The value of the parent node is greater than the value of each child node

Generally used in the following scenarios:

  • Quick sort (Max and min)
  • Priority queue

Maximum heap/minimum heap

The SPLHEAP abstract class in SPL implements the heap data structure. SPLMAXHEAP and SPLMINHEAP inherit from SPLHEAP and are used to implement maximum and minimum heaps, respectively. The following code takes the maximum heap as an example. The minimum heap is similar to the maximum heap

$maxHeap = new splmaxHeap (); $maxheap->insert(12); $maxheap->insert(12); $maxheap->insert(3); $maxheap->insert(222); $maxheap->insert(2); $maxheap->insert(312); $maxheap->insert(3); $maxheap->insert(13); $maxheap->insert(32); $maxheap->insert(3); $maxheap->insert(1); Echo ". $maxheap->top().php_eol; $maxheap->extract().php_eol; $maxheap->extract().php_eol; Echo "extract: ". $maxheap->extract().php_eol; Echo "extract: ". $maxheap->extract().php_eol; Echo "empty heap:".php_eol; var_dump($maxheap->isEmpty()); $maxheap->count().php_eol; $maxheap->count().php_eol; $maxheap->count().php_eol;

Implement custom push sort

Many times, the sheer number size comparison does not satisfy our requirements for the heap data structure. Let’s say we want to do heap sort on a complex array. The SplHeap class provides the abstract compare method, and as long as we implement our own compare method, we can sort the minimum heap to the maximum heap on any data type

Class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * If you want to get a class mmaxHead extends SplHeap {/** * @param mixed $value2 * * @return int */ protected function compare($value1, $value2) { if ($value1['score'] > $value2['score']) { return 1; } elseif ($value1['score'] < $value2['score']) { return -1; } else { return 0; } } } $myheap = new MmaxHead(); $myheap->insert(['name' => "bob1", "score" => 65]); $myheap - > insert ([' name '= > "bob2", "score" = > 34.3]). $myheap - > insert ([' name '= > "bob3", "score" = > 99.3]). $myheap - > insert ([' name '= > "bob4", "score" = > 23.4]). $myheap->insert(['name' => "bob5", "score" => 55]); $myheap->insert(['name' => "bob6", "score" => 66]); Echo "The highest score is".php_eol; var_dump($myheap->top()); Echo "rank:".php_eol; while (! $myheap->isEmpty()) { var_dump($myheap->extract()); }

Priority queue

The SPL already provides us with a priority queue, SplPriorityQueue. SplPriorityQueue is implemented based on the maximum heap, i.e. the higher the priority, the first to queue. You can implement your own business logic by overwriting Compare to make it a low priority first out (minimum heap). You can also implement your own business logic by integrating rewrite Compare

$objPQ = new SplPriorityQueue(); $objPQ->insert('A',3); $objPQ->insert('B',6); $objPQ->insert('C',1); $objPQ->insert('D',2); $objpq-> count().php_eol; $objpq-> count().php_eol; /** * Set element unqueuing mode * SplPriorityQueue::EXTR_DATA extract value * SplPriorityQueue::EXTR_DATA extract priority * SplPriorityQueue::EXTR_BOTH */ / default $objpq-> setExtractFlags(SplPriorityQueue::EXTR_DATA); $objpq-> top().php_eol; $objpq-> top().php_eol; $objPQ->setExtractFlags(SplPriorityQueue::EXTR_PRIORITY); $objpq-> top().php_eol; $objpq-> top().php_eol; $objPQ->setExtractFlags(SplPriorityQueue::EXTR_BOTH); Echo "top "returns an array containing values and priorities:".php_eol; var_dump($objPQ->top()); $objpq-> setExtractFlags(SplPriorityQueue::EXTR_DATA); while($objPQ->valid()){ print_r($objPQ->current()); $objPQ->next(); }

SPL Data Structure 3-SplFixedArray (SPL) Data Structure 3-SplFixedArray (SPLFIXEDARRAY