Structure de données PHP : le secret de la structure des données en tas, permettant un tri efficace et une file d'attente prioritaire

La structure de données du tas en PHP est une structure arborescente qui satisfait aux propriétés complètes de l'arbre binaire et du tas (la valeur du nœud parent est supérieure/inférieure à la valeur du nœud enfant) et est implémentée à l'aide d'un tableau. Le tas prend en charge deux opérations : le tri (extraction du plus grand élément de petit à grand) et la file d'attente prioritaire (extraction du plus grand élément en fonction de la priorité). Les propriétés du tas sont conservées respectivement via les méthodes heapifyUp et heapifyDown.

Structure de données de tas en PHP : Révéler les secrets du tri et des files d'attente prioritaires

Le tas est une structure de données arborescente qui satisfait les deux propriétés suivantes :

• Arbre binaire complet Propriété : arbre Chaque nœud a deux nœuds enfants ou aucun nœud enfant, formant un arbre binaire complet.
• Propriétés du tas : La valeur de chaque nœud parent est supérieure (ou égale à) la valeur de ses deux nœuds enfants (tas max) ou inférieure (ou égale à) la valeur de ses deux nœuds enfants (tas min ) .

Implémentation PHP

En PHP, nous utilisons des tableaux pour implémenter le tas. Ce qui suit est une implémentation PHP d'un tas max :

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);
        }
    }
}

Cas réel

Tri :

$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() . " ";
}

Sortie : 15 12 10 8 5

File d'attente prioritaire :

$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";
}

Sortie :
Servir l'élément 5
Servir l'élément 3
Servir l'élément 2
Servir l'élément 1

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!