PHPAPI优先级队列怎么实现

本文目录导读：

1. 使用 SplPriorityQueue（推荐）
2. 自定义优先级队列实现
3. 使用数组实现简单优先级队列
4. 任务调度器示例
5. 带权重的优先级队列
6. 性能对比
7. 最佳实践建议

在PHP中，实现优先级队列有多种方法,以下是几种常见的实现方式：

使用 SplPriorityQueue（推荐）

PHP 内置的 SplPriorityQueue 是最简单的实现方式：

<?php
class PriorityQueueDemo {
    private $queue;
    public function __construct() {
        $this->queue = new SplPriorityQueue();
    }
    public function enqueue($value, $priority) {
        // 注意：SplPriorityQueue 默认是最大优先级优先
        $this->queue->insert($value, $priority);
    }
    public function dequeue() {
        if (!$this->queue->isEmpty()) {
            return $this->queue->extract();
        }
        return null;
    }
    public function processAll() {
        while (!$this->queue->isEmpty()) {
            echo $this->queue->extract() . "\n";
        }
    }
}
// 使用示例
$queue = new PriorityQueueDemo();
$queue->enqueue("普通任务", 1);
$queue->enqueue("紧急任务", 100);
$queue->enqueue("次要任务", 0);
$queue->enqueue("重要任务", 50);
$queue->processAll();
// 输出: 紧急任务 重要任务 普通任务 次要任务

自定义优先级队列实现

如果需要更多控制,可以实现自己的优先级队列：

<?php
class CustomPriorityQueue {
    private $heap = [];
    public function enqueue($element, $priority) {
        $this->heap[] = [
            'element' => $element,
            'priority' => $priority
        ];
        $this->siftUp(count($this->heap) - 1);
    }
    public function dequeue() {
        if (empty($this->heap)) {
            return null;
        }
        $root = $this->heap[0];
        $last = array_pop($this->heap);
        if (!empty($this->heap)) {
            $this->heap[0] = $last;
            $this->siftDown(0);
        }
        return $root['element'];
    }
    private function siftUp($index) {
        while ($index > 0) {
            $parentIndex = intval(($index - 1) / 2);
            if ($this->heap[$index]['priority'] <= $this->heap[$parentIndex]['priority']) {
                break;
            }
            // 交换
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$parentIndex];
            $this->heap[$parentIndex] = $temp;
            $index = $parentIndex;
        }
    }
    private function siftDown($index) {
        $size = count($this->heap);
        while (true) {
            $largest = $index;
            $left = 2 * $index + 1;
            $right = 2 * $index + 2;
            if ($left < $size && $this->heap[$left]['priority'] > $this->heap[$largest]['priority']) {
                $largest = $left;
            }
            if ($right < $size && $this->heap[$right]['priority'] > $this->heap[$largest]['priority']) {
                $largest = $right;
            }
            if ($largest === $index) {
                break;
            }
            // 交换
            $temp = $this->heap[$index];
            $this->heap[$index] = $this->heap[$largest];
            $this->heap[$largest] = $temp;
            $index = $largest;
        }
    }
    public function isEmpty() {
        return empty($this->heap);
    }
    public function count() {
        return count($this->heap);
    }
}

使用数组实现简单优先级队列

对于简单场景,可以使用数组排序：

<?php
class SimplePriorityQueue {
    private $items = [];
    public function enqueue($value, $priority) {
        $this->items[] = [
            'value' => $value,
            'priority' => $priority
        ];
        // 按优先级降序排序
        usort($this->items, function($a, $b) {
            return $b['priority'] <=> $a['priority'];
        });
    }
    public function dequeue() {
        if (empty($this->items)) {
            return null;
        }
        $item = array_shift($this->items);
        return $item['value'];
    }
    public function peek() {
        if (empty($this->items)) {
            return null;
        }
        return $this->items[0]['value'];
    }
}

任务调度器示例

一个实用的优先级队列应用示例：

<?php
class TaskScheduler {
    private $queue;
    public function __construct() {
        $this->queue = new SplPriorityQueue();
    }
    public function addTask(string $taskName, callable $task, int $priority) {
        $this->queue->insert([
            'name' => $taskName,
            'task' => $task
        ], $priority);
    }
    public function executeAll() {
        $this->queue->setExtractFlags(SplPriorityQueue::EXTR_DATA);
        while (!$this->queue->isEmpty()) {
            $taskData = $this->queue->extract();
            echo "执行任务: {$taskData['name']}\n";
            // 执行任务
            call_user_func($taskData['task']);
        }
    }
}
// 使用示例
$scheduler = new TaskScheduler();
// 添加不同优先级的任务
$scheduler->addTask("发送邮件通知", function() {
    echo "  发送邮件完成\n";
}, 50);
$scheduler->addTask("处理支付", function() {
    echo "  处理支付完成\n";
}, 100); // 最高优先级
$scheduler->addTask("更新日志", function() {
    echo "  更新日志完成\n";
}, 10);
$scheduler->executeAll();

带权重的优先级队列

<?php
class WeightedPriorityQueue {
    private $queue;
    private $counter = 0;
    public function __construct() {
        $this->queue = new SplPriorityQueue();
    }
    public function enqueue($value, $basePriority, $weight = 1.0) {
        // 计算最终优先级
        $finalPriority = $basePriority * $weight;
        // 使用 counter 确保相同优先级的元素按插入顺序处理
        $this->queue->insert($value, [$finalPriority, -$this->counter]);
        $this->counter++;
    }
    public function dequeue() {
        if (!$this->queue->isEmpty()) {
            return $this->queue->extract();
        }
        return null;
    }
}

性能对比

最佳实践建议

1. 优先使用 SplPriorityQueue：除非有特殊需求，否则使用 PHP 内置的实现
2. 注意内存管理：处理大量元素时注意内存使用
3. 考虑并发访问：在多线程环境中需要考虑线程安全
4. 错误处理：处理空队列的情况

选择合适的实现方式取决于你的具体需求，如性能要求、灵活性要求和代码复杂性等。