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-tutoriel php-php.cn

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

WBOY

Libérer： 2024-06-01 15:54:01

original

1195 Les gens l'ont consulté

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 PHP : le secret de la structure des données en tas, permettant un tri efficace et une file dattente prioritaire

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

Copier après la connexion

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

Copier après la connexion

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

Copier après la connexion

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!