The main introduction to priority queue, through the priority queue out of the heap, and then write a class (PHP code) to implement a large root heap

For the original article, visit my blog, Tomato Tech Stack

Priority queue

define

Priority queues are abstract data types in computer science. Each element in the priority queue has its own priority, and the element with the highest priority gets the service first. Elements of the same priority are served in the order they are placed in the priority queue. Priority queues are often implemented in a heap.

The characteristics of

  • Common queue: first in first out, last in last out
  • Priority queue: The queue exit order has nothing to do with the queue entry order, but is related to the priority

Real purpose

  • Dynamic Task Processing Center (operating system)

Why use priority queues

The problem

  • Select the top 100 out of 1,000,000 elements
  • Select the first M elements out of N elements

The solution

  • Sorting, time complexity O(NlogN)
  • Using priority queues: Time complexity (NlogM)

Priority queue implementation comparison

The heap

define

The implementation of heap through the construction of binary heap (binary heap), is actually a kind of binary tree; Because of the universality of its application, when not qualified, it refers to this implementation of the data structure. This data structure has the following properties.

  • Any node is less than (or greater than) all of its descendants, and the smallest element (or largest element) is at the root of the heap (heap ordering).
  • The heap is always a complete tree. That is, all nodes except the lowest layer are filled with elements, and the lowest layer is filled as far left as possible to right.
  • The heap with the largest root node is called the maximum heap or large root heap, and the heap with the smallest root node is called the minimum heap or small root heap. Common heap have binary heap, Fibonacci heap and so on.

Use arrays to store binary heaps

Code implementation


      
require('.. /Library/SortTestHelper.php');
/** * Max */
class MaxHeap{


	private $data;
	private $count;

	public function __construct(a){
		$this->data = array(a);$this->count = 0;
	}


	// public function __construct($arr){
	// }

	public function insert($item){

		// Start at 1
        $this->data[$this->count + 1] = $item;
        $this->_shiftUp($this->count+1);
        $this->count++;
    }

    public function  extractMax(a){
        $ret = $this->data[1];
        swap( $this->data, 1 , $this->count);
        $this->count--;
        $this->_shiftDown(1);
        return $ret;
    }

    public function getMax(a){
        return $this->data[1];
    }

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

    public function getData(a){
    	return $this->data;
    }

    /** * [_shiftUp puts the newly added element directly after the array, and then compares it with the parent element to the root node] *@param  [type] $k [description]
     * @return [type]    [description]
     */
	private function _shiftUp($k){
		// If the value of the leaf node is larger than the parent element, swap places and update the value of k
        while( $k > 1 && $this->data[(int)($k/2)]"$this->data[$k] ){
            // swap( $this->data[(int)($k/2)], $this->data[$k] );
            swap( $this->data, (int)($k/2) , $k);
            $k = (int)($k/2); }}/** * [_shiftDown when an element is released from the heap, the value is still a large root heap. The final value of the array element is swapped with the first value, and the nature of the heap is maintained from top to bottom@param  [type] $k [description]
     * @return [type]    [description]
     */
    private function _shiftDown($k){
    	//2k represents the left child of this node
        while( 2*$k <= $this->count ){
            $j = 2*$k;
            // Check whether the right node exists and the right node is larger than the left node
            if( $j+1< =$this->count && $this->data[$j+1] > $this->data[$j] ) $j ++;
            if( $this->data[$k] >= $this->data[$j] ) break;
            // swap( $this->data[$k] , $this->data[$j] );
            swap( $this->data, $k , $j );
            $k = $j;
        }
    }
}

$head_obj = new MaxHeap();
$n = 10;
for ($i=0; $i < $n; $i++) {
	$head_obj -> insert(rand(0.1000));
}

print_r($head_obj -> getData());

while(! $head_obj -> isEmpty()) {echo $head_obj -> extractMax()."\n";
}
? >

Copy the code

The results of

The resulting heap is:Array([1] = >916
    [2] = >776
    [3] = >590
    [4] = >615
    [5] = >764
    [6] = >539
    [7] = >95
    [8] = >167
    [9] = >23
    [10] = >374) Prints the big root heap as:916
776
764
615
590
539
374
167
95
23
Copy the code

— — — — — — — — — — — — — — — — — — — — — — — — — gorgeous line — — — — — — — — — — — — — — — — — — — —

After watching the friends can click a like/follow, your support is the biggest encouragement to me.

Personal blog tomato technology small stack and gold digging home page

If you want to know more, please follow my wechat official account: Tomato Technology Xiaozhan