我個(gè)人覺得解釋的很清楚，大家理解起來很簡(jiǎn)單，學(xué)C和匯編語言可能會(huì)更清晰。

什么是堆？堆是一種基于樹抽象數(shù)據(jù)類型的特殊數(shù)據(jù)結(jié)構(gòu)，在許多算法和數(shù)據(jù)結(jié)構(gòu)中都有應(yīng)用。一個(gè)常見的例子是優(yōu)先級(jí)隊(duì)列和堆排序，這是排序算法之一。在本文中，我們將討論堆的屬性、不同類型的堆以及堆的常見操作。此外，我們將學(xué)習(xí)堆排序，我們將使用SPL實(shí)現(xiàn)堆。根據(jù)定義，堆是一種具有堆特性的樹形數(shù)據(jù)結(jié)構(gòu)。如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)，稱為最大堆，如果父節(jié)點(diǎn)小于子節(jié)點(diǎn)，稱為最小堆。

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

堆的結(jié)構(gòu)有很多種，比如二進(jìn)制堆、B堆、斐波那契堆、三進(jìn)制堆、樹堆、弱堆等等。二進(jìn)制堆是最流行的堆實(shí)現(xiàn)之一。二進(jìn)制堆是一個(gè)完整的二叉樹，樹的所有內(nèi)部節(jié)點(diǎn)都被完全填充，最后一層可以完全填充，也可以部分填充。對(duì)于二進(jìn)制堆，我們可以以對(duì)數(shù)時(shí)間復(fù)雜度執(zhí)行大部分操作。

堆的操作

堆是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)。我們首先基于給定的數(shù)據(jù)構(gòu)建一個(gè)堆。因?yàn)槎延袊?yán)格的構(gòu)造規(guī)則，我們操作的每一步都要符合這個(gè)規(guī)則。下面是堆的一些核心操作。

創(chuàng)建堆插入新值從堆中提取最小值或最大值刪除一個(gè)值交換

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

在插入節(jié)點(diǎn)時(shí)，我們不能從任何節(jié)點(diǎn)開始。插入操作如下

將新節(jié)點(diǎn)插入堆的底部檢查新節(jié)點(diǎn)和父節(jié)點(diǎn)的大小順序，如果它們是正確的順序，停止。如果它們不是正確的順序，交換它們?nèi)缓罄^續(xù)前一步的檢查。這一步驟與前一步一起被稱為篩分或上升，等等。

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

從堆移動(dòng)最后一個(gè)節(jié)點(diǎn)作為新根將新根節(jié)點(diǎn)與子節(jié)點(diǎn)進(jìn)行比較，如果它們處于正確的順序，則停止。如果不是，則將根節(jié)點(diǎn)與子節(jié)點(diǎn)交換（當(dāng)是小根堆時(shí)為最小子節(jié)點(diǎn)，當(dāng)大根堆時(shí)為最大子節(jié)點(diǎn)）并繼續(xù)前面的步驟。這一步與前一個(gè)步驟一起被稱為下堆。

在堆中，一個(gè)重要的操作是交換。現(xiàn)在我們將使用PHP7實(shí)現(xiàn)二進(jìn)制堆。

& lt？服務(wù)器端編程語言（Professional Hypertext Preprocessor的縮寫）

命名空間DataStructureHeap

類MaxHeap

{

public $ heap

public $ count

public function _ _ construct(int $ size)

{

//初始化堆

$this->。heap = array_fill( 0，$size，0)；

$this->。count = 0；

}

創(chuàng)建公共函數(shù)(array $arr = [])

{

array_map(函數(shù)($item){

$this->。插入($ item)；

}，$ arr)；

}

公共函數(shù)插入(int $data)

{

//插入數(shù)據(jù)操作

if($ this->；count == 0) {

//插入第一個(gè)數(shù)據(jù)

$this->。堆[0]= $ data；

$this->。count = 1；

} else {

//將新插入的數(shù)據(jù)放在堆的后面

$this->。heap[ $this->count++] = $ data；

//浮動(dòng)到正確的位置

$this->。siftUp()；

}

}

公共功能顯示()

{

返回內(nèi)爆( "，array _ slice($ this->；heap，0))；

}

公共職能siftUp()

{

//要浮動(dòng)的元素的臨時(shí)位置

$ TempPos = $ this->；count-1；

//根據(jù)完全二叉樹的性質(zhì)找到次節(jié)點(diǎn)的位置

$ ParentPos = int val($ TempPos/2)；

while($ TempPos & gt；0 & amp& amp$this->。堆[$ ParentPos]& lt；$this->。堆[ $tempPos]) {

//當(dāng)不是根節(jié)點(diǎn)且次節(jié)點(diǎn)的值小于臨時(shí)節(jié)點(diǎn)的值時(shí)，交換兩個(gè)節(jié)點(diǎn)的值

$this->。swap( $parentPos，$ TempPos)；

//重置浮動(dòng)元素的位置

$ tempPos = $ parentPos

//重置父節(jié)點(diǎn)的位置

$ ParentPos = int val($ TempPos/2)；

}

}

公共函數(shù)交換(int $a，int $b)

{

$temp = $this->堆[$ a]；

$this->。heap[ $a] = $this->堆[$ b]；

$this->。heap[$ b]= $ temp；

}

公共函數(shù)extractMax()

{

//最大值是大跟堆的第一個(gè)值

$max = $this->。堆[0]；

//使用堆的最后一個(gè)元素作為臨時(shí)根節(jié)點(diǎn)

$this->。heap[ 0] = $this->heap[ $this->count-1]；

//將最后一個(gè)節(jié)點(diǎn)重置為0

$this->。heap[-$ this->；count]= 0；

//將根節(jié)點(diǎn)下沉到正確的位置

$this->。sift down(0)；

return $ max

}

公共函數(shù)siftDown(int $k)

{

//最大值的位置

$最大= $ k；

//左邊孩子的位置

$ left = 2 * $ k+1；

//右邊孩子的位置

$ right = 2 * $ k+2；

if($ left & lt；$this->。計(jì)數(shù)和。& amp$this->。heap[$最大] <。$this->。heap[ $left]) {

//如果左子項(xiàng)大于最大值，則將最大值重置為左子項(xiàng)

$最大= $左；

}

if($ right & lt；$this->。計(jì)數(shù)和。& amp$this->。heap[$最大] <。$this->。heap[ $right]) {

//如果右邊的子級(jí)大于最大值，則將最大值重置為左邊的子級(jí)

$最大= $右；

}

//如果最大值的位置發(fā)生變化，

if($最大！= $k) {

//互換頭寸

$this->。swap(最大，k美元)；

//繼續(xù)下沉，直到初始位置不變

$this->。sift down($最大)；

}

}

}復(fù)雜性分析

因?yàn)椴煌N類的堆有不同的實(shí)現(xiàn)，所以不同的堆實(shí)現(xiàn)有不同的復(fù)雜性。然而，在各種實(shí)現(xiàn)中，堆的操作都是O(1)復(fù)雜度，即獲取最大值或最小值。我來看看二進(jìn)制堆的復(fù)雜度分析。

因?yàn)槎M(jìn)制堆沒有完全排序，所以搜索操作將比二叉查找樹花費(fèi)更多的時(shí)間。

堆和優(yōu)先級(jí)隊(duì)列

最常見的操作之一是將堆用作優(yōu)先級(jí)隊(duì)列。在PHP實(shí)現(xiàn)棧和PHP實(shí)現(xiàn)隊(duì)列中，我們了解到優(yōu)先級(jí)隊(duì)列是根據(jù)元素的權(quán)重而不是隊(duì)列順序出列的結(jié)構(gòu)。我們用鏈表和Spl實(shí)現(xiàn)了優(yōu)先級(jí)隊(duì)列?，F(xiàn)在我們使用堆來實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列。

& lt？服務(wù)器端編程語言（Professional Hypertext Preprocessor的縮寫）

命名空間DataStructureHeap

類優(yōu)先級(jí)隊(duì)列擴(kuò)展了最大堆

{

public function _ _ construct(int $ size)

{

parent::_ _ construct($ size)；

}

公共函數(shù)排隊(duì)(int $val)

{

parent::insert($ val)；

}

公共函數(shù)出列()

{

return parent::ExtractMax()；

}

}堆排序

在堆排序中，我們需要構(gòu)建一個(gè)給定值的堆。然后不斷檢查堆的值，確保整個(gè)堆隨時(shí)排序。在正常的堆結(jié)構(gòu)中，每當(dāng)我們?cè)谶m當(dāng)?shù)奈恢貌迦胍粋€(gè)新值時(shí)，我們就停止檢查，但是在堆排序中，只要有下一個(gè)值，我們就一直檢查構(gòu)建堆。偽代碼如下:

//你可能看不懂?？梢蕴^。

HeapSort(A)

構(gòu)建堆(一)

對(duì)于i = n -1至0

交換(A[ 0]，A[1])

n = n - 1

Heapify(A，0)

構(gòu)建堆(一)

n = elemens_in(A)

對(duì)于i = floor(n / 2)至0

健康(甲，乙)

健康(甲，乙)

left = 2i+1；

right = 2i+2；

max = i

if(左& ltn和A[左]>;A[i])

max =左側(cè)

if(右& ltn和A[右]>;A[max])

max =右側(cè)

if (max！= i)

互換(A[i]，A[max])

健康(A，最大值)

從上面的偽代碼可以看出，堆排序的第一步是構(gòu)建一個(gè)堆。每次我們向堆中添加新元素時(shí)，我們都會(huì)調(diào)用heapify來滿足堆的特性。一旦建立了堆，我們檢查所有的元素，然后使用PHP對(duì)堆進(jìn)行排序。

函數(shù)heapSort(& amp；$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)；

}

}

函數(shù)BuildHeap(& amp；$arr)

{

$ length = count($ arr)；

$ HeaPsize = $ length-1；

for($ I =($ length/2)；$i >。= 0;$i - ) {

heapify( $i，$heapSize，$ arr)；

}

}

函數(shù)heapify(int $k，int $heapSize，array & amp$arr)

{

$最大= $ k；

$ left = 2 * $ k+1；

$ right = 2 * $ k+2；

if($ left & lt；= $ heapSize & amp& amp$arr[ $k] <。$arr[ $left]) {

$最大= $左；

}

if($ right & lt；= $ heapSize & amp& amp$ arr[$最大] <。$arr[ $right]) {

$最大= $右；

}

if($最大！= $k) {

list($ arr[$最大]，$arr[ $k]) = [ $arr[ $k]，$ arr[$最大]]；

heap ify($最大，$heapSize，$ arr)；

}

}

堆排序的時(shí)間復(fù)雜度為O(nlog n)，空之間的復(fù)雜度為O(1)。與合并排序相比，堆排序具有更好的性能。

PHP中的SplHeap、SplMinHeap和SplMaxHeap

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

建議你多看看棧，別以為自己知道怎么做。事實(shí)上，當(dāng)你在項(xiàng)目中需要它的時(shí)候，會(huì)有很多維修。重要，面試基本都會(huì)問。

猩猩哥哥兼美容設(shè)計(jì)師基維設(shè)計(jì)的t恤

“PHP神Pro”

你活該！