摘要：一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。另外我們還將學(xué)習(xí)堆排序，并將使用實現(xiàn)堆。堆排序在堆排序中，我們需要用給定的值構(gòu)建一個一個堆。偽代碼如下從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個堆。

堆是基于樹抽象數(shù)據(jù)類型的一種特殊的數(shù)據(jù)結(jié)構(gòu)，用于許多算法和數(shù)據(jù)結(jié)構(gòu)中。一個常見的例子就是優(yōu)先隊列，還有排序算法之一的堆排序。這篇文章我們將討論堆的屬性、不同類型的堆以及
堆的常見操作。另外我們還將學(xué)習(xí)堆排序，并將使用SPL實現(xiàn)堆。

根據(jù)定義，堆是一個擁有堆特性的樹形數(shù)據(jù)結(jié)構(gòu)。如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)，那么它被稱為最大堆，如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)，則稱為最小堆。下圖是最大堆的例子

我們看根節(jié)點(diǎn)，值100大于兩個子節(jié)點(diǎn)19和36。對于19來說，該值大于17和3。其他節(jié)點(diǎn)也適用相同的規(guī)則。我們可以看到，這棵樹沒有完全排序。但重要的事實是我們總能找到樹的最大值或最小值，在許多特殊的情況下這是非常有用的。

堆結(jié)構(gòu)有很多種，如二叉堆、B堆、斐波那契堆、三元堆，樹堆、弱堆等。二叉堆是堆實現(xiàn)中最流行的一種。二叉堆是一個完全二叉樹（不了解二叉樹的朋友可以看PHP實現(xiàn)二叉樹），樹的所有內(nèi)部節(jié)點(diǎn)都被完全填充，最后一層可以完全填充的或部分填充。對于二叉堆，我們可以在對數(shù)時間復(fù)雜度內(nèi)執(zhí)行大部分操作。

堆是一個特殊的樹數(shù)據(jù)結(jié)構(gòu)。我們首先根據(jù)給定的數(shù)據(jù)構(gòu)建堆。由于堆有嚴(yán)格的構(gòu)建規(guī)則，所以我們每一步操作都必須滿足這個規(guī)則。下面是堆的一些核心操作。

創(chuàng)建堆

插入新值

從堆中提取最小值或最大值

刪除一個值

交換

從給定的項或數(shù)字集合創(chuàng)建堆需要我們確保堆規(guī)則和二叉樹屬性得到滿足。這意味著父節(jié)點(diǎn)必須大于或小于子節(jié)點(diǎn)。對于樹中的所有節(jié)點(diǎn)，都需要遵守這個規(guī)則。同樣，樹必須是一個完全的二叉樹。在創(chuàng)建堆時，我們從一個節(jié)點(diǎn)開始，并向堆中插入一個新節(jié)點(diǎn)。

當(dāng)插入節(jié)點(diǎn)操作時，我們不能從任意節(jié)點(diǎn)開始。插入操作如下

將新節(jié)點(diǎn)插入堆的底部

檢查新節(jié)點(diǎn)和父節(jié)點(diǎn)的大小順序，如果它們是正確的順序，停止。

如果它們不是正確的順序，交換它們?nèi)缓罄^續(xù)前一步的檢查。這一步驟與前一步一起被稱為篩分或上升，等等。

提取操作（最小或最大）即從堆中取出根節(jié)點(diǎn)。在此之后，我們必須執(zhí)行下列操作以確保剩余節(jié)點(diǎn)然仍符合堆的特點(diǎn)。

從堆移動最后一個節(jié)點(diǎn)作為新根

將新根節(jié)點(diǎn)與子節(jié)點(diǎn)進(jìn)行比較，如果它們處于正確的順序，則停止。

如果不是，則將根節(jié)點(diǎn)與子節(jié)點(diǎn)交換（當(dāng)是小根堆時為最小子節(jié)點(diǎn)，當(dāng)大根堆時為最大子節(jié)點(diǎn)）并繼續(xù)前面的步驟。這一步與前一個步驟一起被稱為下堆。

在堆中，一個重要的操作是交換?，F(xiàn)在我們將使用PHP7來實現(xiàn)二叉堆。

namespace DataStructureHeap;

class MaxHeap
{
    public $heap;
    public $count;

    public function __construct(int $size)
    {
        //初始化堆
        $this->heap = array_fill(0, $size, 0);
        $this->count = 0;
    }

    public function create(array $arr = [])
    {
        array_map(function($item){
            $this->insert($item);
        }, $arr);
    }

    public function insert(int $data)
    {
        //插入數(shù)據(jù)操作
        if ($this->count == 0) {
            //插入第一條數(shù)據(jù)
            $this->heap[0] = $data;
            $this->count = 1;
        } else {
            //新插入的數(shù)據(jù)放到堆的最后面
            $this->heap[$this->count++] = $data;
            //上浮到合適位置
            $this->siftUp();
        }
    }

    public function display()
    {
        return implode(" ", array_slice($this->heap, 0));
    }

    public function siftUp()
    {
        //待上浮元素的臨時位置
        $tempPos = $this->count - 1;    
        //根據(jù)完全二叉樹性質(zhì)找到副節(jié)點(diǎn)的位置
        $parentPos = intval($tempPos / 2);

        while ($tempPos > 0 && $this->heap[$parentPos] < $this->heap[$tempPos]) {
            //當(dāng)不是根節(jié)點(diǎn)并且副節(jié)點(diǎn)的值小于臨時節(jié)點(diǎn)的值，就交換兩個節(jié)點(diǎn)的值
            $this->swap($parentPos, $tempPos);
            //重置上浮元素的位置
            $tempPos = $parentPos;
            //重置父節(jié)點(diǎn)的位置
            $parentPos = intval($tempPos / 2);
        }
    }

    public function swap(int $a, int $b)
    {
        $temp = $this->heap[$a];
        $this->heap[$a] = $this->heap[$b];
        $this->heap[$b] = $temp;
    }

    public function extractMax()
    {
        //最大值就是大跟堆的第一個值
        $max = $this->heap[0];
        //把堆的最后一個元素作為臨時的根節(jié)點(diǎn)
        $this->heap[0] = $this->heap[$this->count - 1];
        //把最后一個節(jié)點(diǎn)重置為0
        $this->heap[--$this->count] = 0;
        //下沉根節(jié)點(diǎn)到合適的位置
        $this->siftDown(0);

        return $max;
    }

    public function siftDown(int $k)
    {
        //最大值的位置
        $largest = $k;
        //左孩子的位置
        $left = 2 * $k + 1;
        //右孩子的位置
        $right = 2 * $k + 2;


        if ($left < $this->count && $this->heap[$largest] < $this->heap[$left]) {
            //如果左孩子大于最大值，重置最大值的位置為左孩子
            $largest = $left;
        }

        if ($right < $this->count && $this->heap[$largest] < $this->heap[$right]) {
            //如果右孩子大于最大值，重置最大值的位置為左孩子
            $largest = $right;
        }


        //如果最大值的位置發(fā)生改變
        if ($largest != $k) {
            //交換位置
            $this->swap($largest, $k);
            //繼續(xù)下沉直到初始位置不發(fā)生改變
            $this->siftDown($largest);
        }
    }
}

因為不同種類的堆有不同的實現(xiàn)，所以各種堆實現(xiàn)也有不同的復(fù)雜度。但是有一個堆的操作在各類實現(xiàn)中都是O(1)的復(fù)雜度，就是獲取最大值或者最小值。我看來看下二分堆的復(fù)雜度分析。

因為二叉堆不是完全排序的，所以搜索操作會比二叉搜索樹花更多的時間。

一個最常用的操作就是將堆當(dāng)作優(yōu)先隊列來使用。在PHP實現(xiàn)棧和PHP實現(xiàn)隊列中，我們已經(jīng)了解到優(yōu)先隊列是一種根據(jù)元素權(quán)重而不是入隊順序來進(jìn)行出隊操作的結(jié)構(gòu)。我們已經(jīng)用鏈表實現(xiàn)優(yōu)先隊列和Spl實現(xiàn)優(yōu)先隊列,現(xiàn)在我們使用堆來實現(xiàn)優(yōu)先隊列。

namespace DataStructureHeap;

class PriorityQueue extends MaxHeap
{
    public function __construct(int $size)
    {
        parent::__construct($size);
    }

    public function enqueue(int $val)
    {
        parent::insert($val);
    }

    public function dequeue()
    {
        return parent::extractMax();
    }
}

在堆排序中，我們需要用給定的值構(gòu)建一個一個堆。然后連續(xù)的檢查堆的值以確保任何時候整個堆都是排序的。在正常的堆結(jié)構(gòu)中，我們每當(dāng)插入一個新的值到合適位置之后就停止檢查，但是在堆排序中，只要有下一個值，我們就不斷的去檢查構(gòu)建堆。偽代碼如下：

HeapSort(A)
BuildHeap(A)
for i = n-1 to 0
swap(A[0],A[i])
n = n - 1
Heapify(A, 0)

BuildHeap(A)
n = elemens_in(A)
for i = floor(n / 2) to 0
Heapify(A, i)

Heapify(A, i)
left = 2i+1;
right = 2i + 2;
max = i

if (left < n and A[left] > A[i])
max = left
if (right < n and A[right] > A[max])
max = right

if (max != i)
swap(A[i], A[max])
Heapify(A, max)

從上面的偽代碼可以看到，堆排序的第一步就是構(gòu)建一個堆。每次我們向堆中添加新的元素，我們都調(diào)用heapify來滿足堆的特性。一旦堆構(gòu)建好之后，我們對所有的元素都進(jìn)行檢查，下面使用PHP的實現(xiàn)堆排序。完整的代碼可以點(diǎn)這里查看。

function heapSort(&$arr)
{
    $length = count($arr);
    buildHeap($arr);
    $heapSize = $length - 1;
    for ($i = $heapSize; $i >= 0; $i--) {
        list($arr[0], $arr[$heapSize]) = [$arr[$heapSize], $arr[0]];
        $heapSize--;
        heapify(0, $heapSize, $arr);
    }
}

function buildHeap(&$arr)
{
    $length = count($arr);
    $heapSize = $length - 1;
    for ($i = ($length / 2); $i >= 0; $i--) {
        heapify($i, $heapSize, $arr);
    }
}

function heapify(int $k, int $heapSize, array &$arr)
{
    $largest = $k;
    $left = 2 * $k + 1;
    $right = 2 * $k + 2;

    if ($left <= $heapSize && $arr[$k] < $arr[$left]) {
        $largest = $left;
    }

    if ($right <= $heapSize && $arr[$largest] < $arr[$right]) {
        $largest = $right;
    }

    if ($largest != $k) {
        list($arr[$largest], $arr[$k]) = [$arr[$k], $arr[$largest]];
        heapify($largest, $heapSize, $arr);
    }
}

堆排序的時間復(fù)雜度為O(nlog n)，空間復(fù)雜度為O(1)。對比歸并排序，堆排序有更好的表現(xiàn)。

當(dāng)然，方便的PHP內(nèi)置的標(biāo)準(zhǔn)庫已經(jīng)幫助我實現(xiàn)了堆，你可以通過SplHeap、SplMinHeap、SplMaxHeap來使用它們。

PHP基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)專題系列目錄: 地址。主要使用PHP語法總結(jié)基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)和算法。還有我們?nèi)粘HP開發(fā)中容易忽略的基礎(chǔ)知識和現(xiàn)代PHP開發(fā)中關(guān)于規(guī)范、部署、優(yōu)化的一些實戰(zhàn)性建議，同時還有對Javascript語言特點(diǎn)的深入研究。