PHP 우선순위 큐 소개(코드 포함)

이 글은 PHP 우선순위 큐(코드 포함)에 대한 소개를 제공합니다. 이는 특정 참고 가치가 있습니다. 도움이 필요한 친구들이 참고할 수 있기를 바랍니다.

PHP의 SPL 라이브러리에는 SplPriorityQueue 우선 순위 대기열이 내장되어 있으며 힙 데이터 구조로 구현됩니다. 기본값은 MaxHeap 모드입니다. 즉, 우선 순위가 클수록 대기열에 우선 순위가 부여됩니다. , MinHeap은 비교 방법을 다시 작성하여 사용할 수 있습니다. (우선 순위가 낮을수록) 팀에서 우선 순위가 높을수록 장면이 더 많아지는 것 같습니다. ㅋㅋㅋ 힙이 파괴되고 그에 따라 힙이 안정적인 상태(MaxHeap 또는 MinHeap)로 조정됩니다. 즉, 힙 상단의 마지막 요소를 교체한 다음, 만족하지 않는 경우 안정적인 상태 검증을 수행합니다. 힙 특성을 계속 조정하지 않으면 안정적인 힙을 얻게 되므로 우선순위가 같은 레벨인 경우 팀 탈퇴 순서는 팀 합류 순서에 따르지 않습니다.

소스 코드 예:

<?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

5개 작업의 우선순위가 동일하더라도 힙의 특성상 큐는 enqueue된 순서대로 데이터를 반환하지 않는 것을 볼 수 있습니다:

1, enqueue task1, task2, task3, task4, task5, 우선순위가 동일하기 때문에 힙은 항상 안정적인 상태였습니다.

2. 대기열을 떠난 후, 힙은 먼저 task5, task2, task3, task4로 구조를 조정하고 안정적인 상태에 도달합니다.

3. 대기열을 떠난 후, 스택은 먼저 task4, task2, task3으로 구조를 조정하고 안정적인 상태에 도달합니다.

4. 대기열을 떠난 후, 힙은 먼저 task3 및 task2로 구조를 조정하고 안정적인 상태에 도달합니다.

5. 대기열을 떠난 후, 스택은 먼저 task2의 구조를 조정하고 안정적인 상태에 도달합니다.

4. 팀을 탈퇴하면 task2가 주어집니다.

Iterator, Countable

SplPriorityQueue는 Iterator, Countable 인터페이스를 구현하므로 foreach/count 함수로 작동하거나 rewind, valid, current, next/count 메서드를 사용할 수 있습니다.

힙 구현이기 때문에 헤드 포인터가 항상 힙의 상단을 가리키기 때문에 되감기 방법은 아무런 효과가 없는 작업입니다. 즉, 현재는 목록과 달리 항상 동일합니다. 는 단지 방황 포인터일 뿐이며 대기열에서 제거되면 삭제됩니다. 힙 요소의 경우 extract = current + next(current는 대기열에서 제거되고 힙에서 삭제됩니다).

<?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가 더 친숙합니다. 즉, 우선순위가 항상 일관되면 힙 조정 기능을 사용하여 데이터가 반환됩니다.

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

맞춤형 우선순위 처리 방법비교 방법을 재정의하여 고유한 우선순위 처리 메커니즘을 정의하세요.

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

이 기사는 여기서 끝났습니다. 더 흥미로운 콘텐츠를 보려면 PHP 중국어 웹사이트의

PHP 비디오 튜토리얼

칼럼을 주목하세요!

위 내용은 PHP 우선순위 큐 소개(코드 포함)의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!