Introduction à la file d'attente prioritaire PHP (avec code)

Cet article vous présente une introduction à la file d'attente prioritaire PHP (avec code). Il a une certaine valeur de référence. Les amis dans le besoin peuvent s'y référer.

La bibliothèque SPL de PHP possède une file d'attente prioritaire SplPriorityQueue intégrée, et elle est implémentée avec la structure de données Heap. La valeur par défaut est le mode MaxHeap, c'est-à-dire que plus la priorité est grande, la priorité est donnée à la file d'attente. Dans le même temps, MinHeap peut être utilisé en réécrivant la méthode de comparaison (plus la priorité est faible, plus la priorité est donnée au retrait de la file d'attente, il semble y avoir très peu de scénarios).

SplPriorityQueue

Fonctionnalités du tas

Vous devez faire attention et comprendre ici : SplPriorityQueue est implémenté comme une structure de données de tas Lorsque nous retirons les éléments de la file d'attente. le haut du tas À ce moment, les caractéristiques du tas sont détruites et le tas sera ajusté en fonction de l'état stable (MaxHeap ou MinHeap), c'est-à-dire que le dernier élément sera remplacé en haut du tas. , puis la vérification de l'état stable sera effectuée si elle ne répond pas aux caractéristiques du tas, continuez à ajuster, ou nous obtiendrons un tas stable, donc lorsque les priorités sont les mêmes, l'ordre de sortie de file d'attente ne suivra pas la mise en file d'attente. commande.

Exemple de code source :

<?php
$splPriorityQueue = new \SplPriorityQueue();
// 设定返回数据的meta信息
// \SplPriorityQueue::EXTR_DATA 默认 只返回数
// \SplPriorityQueue::EXTR_PRIORITY 只返回优先级
// \SplPriorityQueue::EXTR_BOTH 返回数据和优先级
// $splPriorityQueue->setExtractFlags(\SplPriorityQueue::EXTR_DATA);
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 1);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 1);
$splPriorityQueue->insert("task5", 1);

echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;
echo $splPriorityQueue->extract() . PHP_EOL;

//执行结果
task1
task5
task4
task3
task2

Vous pouvez voir que bien que les cinq tâches aient la même priorité, la file d'attente ne renvoie pas les données dans l'ordre dans lequel elles sont mises en file d'attente, en raison de la Caractéristiques du tas : 1. File d'attente task1, task2, task3, task4 et task5. Parce que les priorités sont les mêmes, le tas est toujours dans un état stable.
2. Retirez la file d'attente et récupérez la tâche 1. Le tas ajuste d'abord la structure à la tâche 5, la tâche 2, la tâche 3, la tâche 4 et a atteint un état stable.
3. Retirez la file d'attente et récupérez la tâche 5. La pile ajuste d'abord la structure à la tâche 4, la tâche 2, la tâche 3 et a atteint un état stable.
4. Après avoir quitté la file d'attente, la tâche4 est obtenue. Le tas ajuste d'abord la structure à la tâche3 et à la tâche2, et a atteint un état stable.
5. Retirez la file d'attente et récupérez la tâche 3. La pile ajuste d'abord la structure à la tâche 2 et a atteint un état stable.
4. Quittez l'équipe et obtenez la tâche2.

Iterator, Countable

SplPriorityQueue implémente l'interface Iterator, Countable, nous pouvons donc l'utiliser avec la fonction foreach/count, ou utiliser la méthode rewind, valid, current, next/count.

Notez que parce qu'il s'agit d'une implémentation de tas, la méthode de rembobinage est une opération sans opération qui n'a aucun effet, car le pointeur de tête pointe toujours vers le haut du tas, c'est-à-dire que le courant est toujours égal à top, contrairement à List, qui n'est qu'un pointeur errant. La file d'attente supprimera les éléments du tas, extract = current + next (le courant est retiré de la file d'attente et supprimé du tas).

<?php
$splPriorityQueue = new \SplPriorityQueue();

$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);

echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

// 迭代的话会删除队列元素 current 指针始终指向 top 所以 rewind 没什么意义
for ($splPriorityQueue->rewind(); $splPriorityQueue->valid();$splPriorityQueue->next()) { 
    var_dump($splPriorityQueue->current());
    var_dump($splPriorityQueue->count());
    $splPriorityQueue->rewind();
}

var_dump("is empty:" . $splPriorityQueue->isEmpty());

Extract Dequeue

Extract Dequeue est plus convivial, c'est-à-dire qu'il renvoie toujours l'élément avec la priorité la plus élevée Lorsque les priorités sont les mêmes, le. Le tas sera ajusté. Renvoie les données.

<?php
$splPriorityQueue = new \SplPriorityQueue();

// data  priority
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);

echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

while (! $splPriorityQueue->isEmpty()) {
    var_dump($splPriorityQueue->extract());
    echo $splPriorityQueue->count() . PHP_EOL;
}

Méthode de traitement prioritaire personnalisée

Remplacez la méthode de comparaison pour définir votre propre mécanisme de traitement prioritaire.

<?php
class CustomedSplPriorityQueue extends SplPriorityQueue
{
    public function compare($priority1, $priority2): int
    {
        // return $priority1 - $priority2;//高优先级优先
        return $priority2 - $priority1;//低优先级优先
    }
}

$splPriorityQueue = new \CustomedSplPriorityQueue();
$splPriorityQueue->setExtractFlags(SplPriorityQueue::EXTR_BOTH);
$splPriorityQueue->insert("task1", 1);
$splPriorityQueue->insert("task2", 2);
$splPriorityQueue->insert("task3", 1);
$splPriorityQueue->insert("task4", 4);
$splPriorityQueue->insert("task5", 5);
 
echo "Countable： " . count($splPriorityQueue) . PHP_EOL;

while (!$splPriorityQueue->isEmpty()) {
    var_dump($splPriorityQueue->extract());
}

Cet article est terminé ici. Pour un contenu plus passionnant, vous pouvez faire attention à la colonne

Tutoriel vidéo PHP sur le site Web PHP chinois !

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!