一 、基本數(shù)據(jù)結(jié)構(gòu)

堆：

• 堆是一棵完全二叉樹，
• 根節(jié)點的值總是不大于或者不小于子節(jié)點的值

將根結(jié)點最大的堆叫做最大堆、大頂堆或大根堆，根結(jié)點最小的堆叫做最小堆、小頂堆或小根堆。常見的堆有二叉堆、斐波那契堆
通常堆頂節(jié)點都是最大或者最小的，在解決特殊問題時，先彈出堆頂元素非常有優(yōu)勢

棧：

先進后出（FILO），就像一個敞口向上的容器，只能將后進入容器的先彈出。

隊列：

先進先出（FIFO），跟棧相反，隊列就像一根上下貫通的水管，只能將先流入水管的水流出去。

二、優(yōu)先級隊列

優(yōu)先隊列也是一種數(shù)據(jù)結(jié)構(gòu)，通過加權(quán)值進行排序，PHP核心庫提供了SplPriorityQueue對象來實現(xiàn)。
優(yōu)先隊列內(nèi)部是用Heap：堆這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)的，默認是大頂堆（MaxHeap）。

1. 常規(guī)用法（大頂堆）

$queue = new SplPriorityQueue;

// 插入堆，并自動篩選和排序
// 接受2個參數(shù)，insert(值, 優(yōu)先級)
$queue->insert('A', 3);
$queue->insert('B', 9);
$queue->insert('C', 2);
$queue->insert('D', 5);

// 堆中元素的個數(shù)
$count = $queue->count(); // 此時為4

// 返回堆頂?shù)墓?jié)點
$top = $queue->top(); // 堆不變

/**
* 設(shè)置元素出隊模式
* SplPriorityQueue::EXTR_DATA 僅提取值
* SplPriorityQueue::EXTR_PRIORITY 僅提取優(yōu)先級
* SplPriorityQueue::EXTR_BOTH 提取數(shù)組包含值和優(yōu)先級
*/
$queue->setExtractFlag(SplPriorityQueue::EXTR_BOTH);

// 從堆頂提取元素，并重新篩選和排序
$queue->extract(); // 此時B被取出，堆頂元素重置為D
$queue->extract(); // 此時D被取出，堆頂元素重置為A
$queue->extract(); // 此時A被取出，堆頂元素重置為C
$queue->extract(); // 此時C被取出，堆中元素全部取出

// 判斷堆是否為空
$status = $queue->isEmpty(); // 結(jié)果為true

// 迭代指針相關(guān)

// 因為優(yōu)先隊列是堆實現(xiàn)的，所以rewind實際沒什么用，他永遠指向堆頂指針，current也永遠等于堆頂?shù)闹?// 故而extract相當于current(返回當前節(jié)點)和next(指向下一個節(jié)點)兩個操作

// 返回當前節(jié)點
$current = $queue->current();

// 指針指向下一個節(jié)點
$queue->next();

// 返回堆中堆中是否還有節(jié)點
while ($queue->valid()) {
    $current = $queue->current();
    $queue->next();
}

2. 改成小頂堆（MinHeap）

優(yōu)先隊列改成小頂堆，需要重寫compare方法，將比較值對調(diào)，即可切換小頂堆和大頂堆。

/*
 * 小頂堆
 */
class MyMinHeap extends SplPriorityQueue {
    function compare($value1, $value2) {
        // if ($value1 === $value1) return 0;
        // return $value1 < $value2 ? -1 : 1; 
        // return $value1 - $value2; // 高優(yōu)先級優(yōu)先
        return $value2 - $value1; // 低優(yōu)先級優(yōu)先
    }
}

$queue = new MyMinHeap;

// 插入堆，并自動篩選和排序
// insert接受2個參數(shù)，key在前，value在后，vaue為排序的權(quán)重值
$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(); // 結(jié)果為true

三、堆、大頂堆和小頂堆

堆就是為了實現(xiàn)優(yōu)先隊列而設(shè)計的一種數(shù)據(jù)結(jié)構(gòu)，它分為大頂堆和小頂堆，PHP核心庫提供了大頂堆SplMaxHeap和小頂堆SplMinHeap兩種類可供直接使用，他們都是由SplHeap抽象類實現(xiàn)的。

• 簡單數(shù)據(jù)

/**
 * 自定義：最小堆/小頂堆
 * 低優(yōu)先級優(yōu)先彈出
 * 等同于系統(tǒng)自帶的SplMinHeap
 */
class MyMinHeap extends SplHeap
{
    // 比較元素，以便在篩選時將它們正確地放在堆中，
    // 如果value1大于value2則為正整數(shù)，如果相等則為0，否則為負整數(shù)
    function compare($value1, $value2) { 
        return $value2 - $value1;
    } 
}

/**
 * 自定義：最大堆/大頂堆
 * 高優(yōu)先級優(yōu)先彈出
 * 等同于系統(tǒng)自帶的SplMaxHeap
 */
class MyMaxHeap extends SplHeap
{
    // 比較元素，以便在篩選時將它們正確地放在堆中，
    // 如果value1小于value2則為正整數(shù)，如果相等則為0，否則為負整數(shù)
    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被取出

• 復(fù)雜數(shù)據(jù)

/**
 * 自定義：最小堆/小頂堆
 * 低優(yōu)先級優(yōu)先彈出
 * 等同于系統(tǒng)自帶的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;
    } 
}

/**
 * 自定義：最大堆/大頂堆
 * 高優(yōu)先級優(yōu)先彈出
 * 等同于系統(tǒng)自帶的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;// 高優(yōu)先級優(yōu)先彈出
        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被取出

總結(jié)：

• 優(yōu)先隊列SplPriorityQueue的insert接受兩個參數(shù)，第一個參數(shù)為值，第二個參數(shù)為權(quán)重
• 大頂堆SplMaxHeap和小頂堆SplMinHeap均實現(xiàn)了SplHeap抽象類，通過重寫compare方法來區(qū)分大/小頂堆
• 大頂堆和小頂堆只接受一個參數(shù)，需要注意傳不同類型的數(shù)據(jù)時，compare方法的寫法需要對應(yīng)地進行修改