PHP优先队列、二叉堆、大顶堆、小顶堆

一 、基本数据结构

堆：

• 堆是一棵完全二叉树，
• 根节点的值总是不大于或者不小于子节点的值

将根结点最大的堆叫做最大堆、大顶堆或大根堆，根结点最小的堆叫做最小堆、小顶堆或小根堆。常见的堆有二叉堆、斐波那契堆
通常堆顶节点都是最大或者最小的，在解决特殊问题时，先弹出堆顶元素非常有优势

栈：

先进后出（FILO），就像一个敞口向上的容器，只能将后进入容器的先弹出。

队列：

先进先出（FIFO），跟栈相反，队列就像一根上下贯通的水管，只能将先流入水管的水流出去。

二、优先级队列

优先队列也是一种数据结构，通过加权值进行排序，PHP核心库提供了SplPriorityQueue对象来实现。
优先队列内部是用Heap：堆这种数据结构来实现的，默认是大顶堆（MaxHeap）。

1. 常规用法（大顶堆）

$queue = new SplPriorityQueue;

// 插入堆，并自动筛选和排序
// 接受2个参数，insert(值, 优先级)
$queue->insert('A', 3);
$queue->insert('B', 9);
$queue->insert('C', 2);
$queue->insert('D', 5);

// 堆中元素的个数
$count = $queue->count(); // 此时为4

// 返回堆顶的节点
$top = $queue->top(); // 堆不变

/**
* 设置元素出队模式
* SplPriorityQueue::EXTR_DATA 仅提取值
* SplPriorityQueue::EXTR_PRIORITY 仅提取优先级
* SplPriorityQueue::EXTR_BOTH 提取数组包含值和优先级
*/
$queue->setExtractFlag(SplPriorityQueue::EXTR_BOTH);

// 从堆顶提取元素，并重新筛选和排序
$queue->extract(); // 此时B被取出，堆顶元素重置为D
$queue->extract(); // 此时D被取出，堆顶元素重置为A
$queue->extract(); // 此时A被取出，堆顶元素重置为C
$queue->extract(); // 此时C被取出，堆中元素全部取出

// 判断堆是否为空
$status = $queue->isEmpty(); // 结果为true

// 迭代指针相关

// 因为优先队列是堆实现的，所以rewind实际没什么用，他永远指向堆顶指针，current也永远等于堆顶的值
// 故而extract相当于current(返回当前节点)和next(指向下一个节点)两个操作

// 返回当前节点
$current = $queue->current();

// 指针指向下一个节点
$queue->next();

// 返回堆中堆中是否还有节点
while ($queue->valid()) {
    $current = $queue->current();
    $queue->next();
}

2. 改成小顶堆（MinHeap）

优先队列改成小顶堆，需要重写compare方法，将比较值对调，即可切换小顶堆和大顶堆。

/*
 * 小顶堆
 */
class MyMinHeap extends SplPriorityQueue {
    function compare($value1, $value2) {
        // if ($value1 === $value1) return 0;
        // return $value1 < $value2 ? -1 : 1; 
        // return $value1 - $value2; // 高优先级优先
        return $value2 - $value1; // 低优先级优先
    }
}

$queue = new MyMinHeap;

// 插入堆，并自动筛选和排序
// insert接受2个参数，key在前，value在后，vaue为排序的权重值
$queue->insert('A', 3);
$queue->insert('B', 9);
$queue->insert('C', 2);
$queue->insert('D', 5);

$queue->extract(); // 此时C被取出，堆顶元素重置为A
$queue->extract(); // 此时A被取出，堆顶元素重置为D
$queue->extract(); // 此时D被取出，堆顶元素重置为B
$queue->extract(); // 此时B被取出，堆中元素全部取出

$status = $queue->isEmpty(); // 结果为true

三、堆、大顶堆和小顶堆

堆就是为了实现优先队列而设计的一种数据结构，它分为大顶堆和小顶堆，PHP核心库提供了大顶堆SplMaxHeap和小顶堆SplMinHeap两种类可供直接使用，他们都是由SplHeap抽象类实现的。

• 简单数据

/**
 * 自定义：最小堆/小顶堆
 * 低优先级优先弹出
 * 等同于系统自带的SplMinHeap
 */
class MyMinHeap extends SplHeap
{
    // 比较元素，以便在筛选时将它们正确地放在堆中，
    // 如果value1大于value2则为正整数，如果相等则为0，否则为负整数
    function compare($value1, $value2) { 
        return $value2 - $value1;
    } 
}

/**
 * 自定义：最大堆/大顶堆
 * 高优先级优先弹出
 * 等同于系统自带的SplMaxHeap
 */
class MyMaxHeap extends SplHeap
{
    // 比较元素，以便在筛选时将它们正确地放在堆中，
    // 如果value1小于value2则为正整数，如果相等则为0，否则为负整数
    function compare($value1, $value2) { 
        return $value1 - $value2;
    } 
}

$minHeap = new MyMinHeap;
// 插入元素，insert(值)
$minHeap->insert(3);
$minHeap->insert(2);
$minHeap->insert(4);
$minHeap->insert(1);
// 取出元素
$minHeap->extract(); // 1被取出
$minHeap->extract(); // 2被取出
$minHeap->extract(); // 3被取出
$minHeap->extract(); // 4被取出

$maxHeap = new MyMaxHeap;
// 插入元素
$maxHeap->insert(3);
$maxHeap->insert(2);
$maxHeap->insert(4);
$maxHeap->insert(1);
// 取出元素
$maxHeap->extract(); // 4被取出
$maxHeap->extract(); // 3被取出
$maxHeap->extract(); // 2被取出
$maxHeap->extract(); // 1被取出

• 复杂数据

/**
 * 自定义：最小堆/小顶堆
 * 低优先级优先弹出
 * 等同于系统自带的SplMinHeap
 */
class MyMinHeap extends SplHeap
{
    function compare($arr1, $arr2) { 
        $value1 = array_values($arr1);
        $value2 = array_values($arr2);
        if ($value2[0] === $value1[0]) return 0;
        return $value2[0] < $value1[0] ? -1 : 1;
    } 
}

/**
 * 自定义：最大堆/大顶堆
 * 高优先级优先弹出
 * 等同于系统自带的SplMaxHeap
 */
class MyMaxHeap extends SplHeap
{
    function compare($arr1, $arr2) { 
        $value1 = array_values($arr1);
        $value2 = array_values($arr2);
        // if ($value2[0] === $value1[0]) return 0;
        // return $value2[0] > $value1[0] ? -1 : 1;// 高优先级优先弹出
        return $value1[0] - $value2[0];
    } 
}

$minHeap = new MyMinHeap;
// 插入元素，insert(值)
$minHeap->insert(['A' => 3]);
$minHeap->insert(['B' => 2]);
$minHeap->insert(['C' => 4]);
$minHeap->insert(['D' => 1]);
// 取出元素
$minHeap->extract(); // D被取出
$minHeap->extract(); // B被取出
$minHeap->extract(); // A被取出
$minHeap->extract(); // C被取出

$maxHeap = new MyMaxHeap;
// 插入元素
$maxHeap->insert(['A' => 3]);
$maxHeap->insert(['B' => 2]);
$maxHeap->insert(['C' => 4]);
$maxHeap->insert(['D' => 1]);
// 取出元素
$maxHeap->extract(); // C被取出
$maxHeap->extract(); // A被取出
$maxHeap->extract(); // B被取出
$maxHeap->extract(); // D被取出

总结：

• 优先队列SplPriorityQueue的insert接受两个参数，第一个参数为值，第二个参数为权重
• 大顶堆SplMaxHeap和小顶堆SplMinHeap均实现了SplHeap抽象类，通过重写compare方法来区分大/小顶堆
• 大顶堆和小顶堆只接受一个参数，需要注意传不同类型的数据时，compare方法的写法需要对应地进行修改