1.7 堆

前面講優(yōu)先隊列的時候提到過堆，因為優(yōu)先隊列可以通過堆來實現(xiàn)，也可以把堆看作是一棵完全二叉樹。堆一般分為兩種，一種是最大堆（有的也叫作大根堆、大頂堆），另一種是最小堆。最大堆根節(jié)點的值是堆中最大的，最小堆根節(jié)點的值是堆中最小的。兩者原理差不多，這里只介紹其中一種，我們就拿最小堆來講解。因為堆是一棵完全二叉樹，所以如果知道子節(jié)點的下標(biāo)，那么一定知道父節(jié)點的下標(biāo)；如果知道父節(jié)點的下標(biāo)，也一定知道子節(jié)點的下標(biāo)（假設(shè)有子節(jié)點），如圖1-59所示。

它們的關(guān)系如下：

1. 在堆中添加元素

堆的常見操作有兩種，一種是往堆中添加元素，另一種是刪除堆頂元素。往堆中添加元素實際上相當(dāng)于在完全二叉樹中添加一個葉子節(jié)點，添加完之后還需要往上調(diào)整，就是和父節(jié)點比較誰的值小（這里介紹的是最小堆），如果比父節(jié)點小，就和父節(jié)點交換，交換完之后，還要繼續(xù)往上比較，如果比父節(jié)點值大，就不再交換，如圖1-60所示。

這樣通過不斷和父節(jié)點比較，如果添加的元素是堆中最小的，它就會跑到根節(jié)點，也就是最小堆的根節(jié)點是堆中所有元素中最小的。如果添加元素不比父節(jié)點小，就不需要交換。

2. 在堆中刪除元素

堆中元素的添加只需要和父節(jié)點比較即可，因為一個節(jié)點最多只能有一個父節(jié)點（根節(jié)點沒有父節(jié)點）。但堆的刪除就有點麻煩了，因為如果直接刪除，就會把一棵二叉樹變成兩棵二叉樹。實際上堆的刪除并不是直接刪除，而是讓最后一個葉子節(jié)點（二叉樹最下面一行最右邊的節(jié)點）替換根節(jié)點，然后根節(jié)點往下調(diào)整，如圖1-61所示，往下調(diào)整的步驟如下：

（1）如果根節(jié)點比它的兩個子節(jié)點都小，就不需要往下調(diào)整。

（2）如果其中的一個子節(jié)點比根節(jié)點小，那么根節(jié)點就和那個比它小的子節(jié)點交換，交換完之后繼續(xù)往下比較。

（3）如果根節(jié)點比它的兩個子節(jié)點都大，那么根節(jié)點就和那個最小的子節(jié)點交換，交換完之后繼續(xù)往下比較。

所以堆的添加會涉及往上調(diào)整，而堆的刪除會涉及往下調(diào)整，這里的刪除只是刪除堆頂元素，如果不是堆頂元素，兩個方向都要考慮，我們來看一下代碼。