PHP data structure: The secret of heap data structure, realizing efficient sorting and priority queue

The heap data structure in PHP is a tree structure that satisfies the complete binary tree and heap properties (the parent node value is greater/less than the child node value), and is implemented using an array. The heap supports two operations: sorting (extracting the largest element from small to large) and priority queue (extracting the largest element according to priority). The properties of the heap are maintained through the heapifyUp and heapifyDown methods respectively.

Heap data structure in PHP: Revealing the secrets of sorting and priority queues

The heap is a tree-like data structure , it satisfies the following two properties:

• Complete binary tree properties: Each node in the tree has two child nodes, or has no child nodes, forming a tree Complete binary tree.
• Heap properties: The value of each parent node is greater than (or equal to) the value of its two child nodes (maximum heap) or less than (or equal to) its two children The value of the node (min-heap).

PHP Implementation

In PHP, we use arrays to implement the heap. The following is a maximum heap PHP implementation:

class MaxHeap {
    private $heap = array();
    private $size = 0;

    public function insert($value) {
        $this->heap[$this->size++] = $value;
        $this->heapifyUp($this->size - 1);
    }

    private function heapifyUp($index) {
        if ($index === 0) {
            return;
        }
        $parentIndex = intval(($index - 1) / 2);
        if ($this->heap[$index] > $this->heap[$parentIndex]) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$parentIndex];
            $this->heap[$parentIndex] = $temp;
            $this->heapifyUp($parentIndex);
        }
    }

    public function extractMax() {
        if ($this->size === 0) {
            return null;
        }
        $max = $this->heap[0];
        $this->heap[0] = $this->heap[$this->size - 1];
        $this->size--;
        $this->heapifyDown(0);
        return $max;
    }

    private function heapifyDown($index) {
        $largestIndex = $index;
        $leftIndex = 2 * $index + 1;
        $rightIndex = 2 * $index + 2;
        if ($leftIndex < $this->size && $this->heap[$leftIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $leftIndex;
        }
        if ($rightIndex < $this->size && $this->heap[$rightIndex] > $this->heap[$largestIndex]) {
            $largestIndex = $rightIndex;
        }
        if ($largestIndex !== $index) {
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$largestIndex];
            $this->heap[$largestIndex] = $temp;
            $this->heapifyDown($largestIndex);
        }
    }
}

Practical case

Sort:

$heap = new MaxHeap();
$heap->insert(10);
$heap->insert(5);
$heap->insert(15);
$heap->insert(8);
$heap->insert(12);

while ($heap->size > 0) {
    echo $heap->extractMax() . " ";
}

Output: 15 12 10 8 5

Priority queue:

$heap = new MaxHeap();
$heap->insert(5);
$heap->insert(2);
$heap->insert(3);
$heap->insert(1);

while ($heap->size > 0) {
    $element = $heap->extractMax();
    echo "服务于元素 " . $element . "\n";
}

Output:
Serving element 5
Serving element 3
Serving element 2
Serve element 1

The above is the detailed content of PHP data structure: The secret of heap data structure, realizing efficient sorting and priority queue. For more information, please follow other related articles on the PHP Chinese website!