二叉堆（Binary Heap）沒(méi)什么神秘，性質(zhì)比二叉搜索樹 BST 還簡(jiǎn)單。其主要操作就兩個(gè)，sink（下沉）和swim（上?。靡跃S護(hù)二叉堆的性質(zhì)。其主要應(yīng)用有兩個(gè)，首先是一種排序方法「堆排序」，第二是一種很有用的數(shù)據(jù)結(jié)構(gòu)「優(yōu)先級(jí)隊(duì)列」。

本文就以實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列（Priority Queue）為例，通過(guò)圖片和人類的語(yǔ)言來(lái)描述一下二叉堆怎么運(yùn)作的。

一、二叉堆概覽

首先，二叉堆和二叉樹有啥關(guān)系呢，為什么人們總數(shù)把二叉堆畫成一棵二叉樹？

因?yàn)?，二叉堆其?shí)就是一種特殊的二叉樹（完全二叉樹），只不過(guò)存儲(chǔ)在數(shù)組里。一般的鏈表二叉樹，我們操作節(jié)點(diǎn)的指針，而在數(shù)組里，我們把數(shù)組索引作為指針：

畫個(gè)圖你立即就能理解了，注意數(shù)組的第一個(gè)索引 0 空著不用：

PS：因?yàn)閿?shù)組索引是數(shù)字，為了方便區(qū)分，將字符作為數(shù)組元素。

你看到了，把 arr[1] 作為整棵樹的根的話，每個(gè)節(jié)點(diǎn)的父節(jié)點(diǎn)和左右孩子的索引都可以通過(guò)簡(jiǎn)單的運(yùn)算得到，這就是二叉堆設(shè)計(jì)的一個(gè)巧妙之處。為了方便講解，下面都會(huì)畫的圖都是二叉樹結(jié)構(gòu)，相信你能把樹和數(shù)組對(duì)應(yīng)起來(lái)。

二叉堆還分為最大堆和最小堆。最大堆的性質(zhì)是：每個(gè)節(jié)點(diǎn)都大于等于它的兩個(gè)子節(jié)點(diǎn)。類似的，最小堆的性質(zhì)是：每個(gè)節(jié)點(diǎn)都小于等于它的子節(jié)點(diǎn)。

兩種堆核心思路都是一樣的，本文以最大堆為例講解。

對(duì)于一個(gè)最大堆，根據(jù)其性質(zhì)，顯然堆頂，也就是 arr[1] 一定是所有元素中最大的元素。

二、優(yōu)先級(jí)隊(duì)列概覽

優(yōu)先級(jí)隊(duì)列這種數(shù)據(jù)結(jié)構(gòu)有一個(gè)很有用的功能，你插入或者刪除元素的時(shí)候，元素會(huì)自動(dòng)排序，這底層的原理就是二叉堆的操作。

數(shù)據(jù)結(jié)構(gòu)的功能無(wú)非增刪查該，優(yōu)先級(jí)隊(duì)列有兩個(gè)主要 API，分別是insert插入一個(gè)元素和delMax刪除最大元素（如果底層用最小堆，那么就是delMin）。

下面我們實(shí)現(xiàn)一個(gè)簡(jiǎn)化的優(yōu)先級(jí)隊(duì)列，先看下代碼框架：

PS：為了清晰起見，這里用到 Java 的泛型，Key可以是任何一種可比較大小的數(shù)據(jù)類型，你可以認(rèn)為它是 int、char 等。

三、實(shí)現(xiàn) swim 和 sink

為什么要有上浮 swim 和下沉 sink 的操作呢？為了維護(hù)堆結(jié)構(gòu)。

我們要講的是最大堆，每個(gè)節(jié)點(diǎn)都比它的兩個(gè)子節(jié)點(diǎn)大，但是在插入元素和刪除元素時(shí)，難免破壞堆的性質(zhì)，這就需要通過(guò)這兩個(gè)操作來(lái)恢復(fù)堆的性質(zhì)了。

對(duì)于最大堆，會(huì)破壞堆性質(zhì)的有有兩種情況：

1. 如果某個(gè)節(jié)點(diǎn) A 比它的子節(jié)點(diǎn)（中的一個(gè)）小，那么 A 就不配做父節(jié)點(diǎn)，應(yīng)該下去，下面那個(gè)更大的節(jié)點(diǎn)上來(lái)做父節(jié)點(diǎn)，這就是對(duì) A 進(jìn)行下沉。

2. 如果某個(gè)節(jié)點(diǎn) A 比它的父節(jié)點(diǎn)大，那么 A 不應(yīng)該做子節(jié)點(diǎn)，應(yīng)該把父節(jié)點(diǎn)換下來(lái)，自己去做父節(jié)點(diǎn)，這就是對(duì) A 的上浮。

當(dāng)然，錯(cuò)位的節(jié)點(diǎn) A 可能要上?。ɑ蛳鲁粒┖芏啻危拍艿竭_(dá)正確的位置，恢復(fù)堆的性質(zhì)。所以代碼中肯定有一個(gè)while循環(huán)。

上浮的代碼實(shí)現(xiàn)：

畫個(gè)圖看一眼就明白了：

下沉的代碼實(shí)現(xiàn)：

下沉比上浮略微復(fù)雜一點(diǎn)，因?yàn)樯细∧硞€(gè)節(jié)點(diǎn) A，只需要 A 和其父節(jié)點(diǎn)比較大小即可；但是下沉某個(gè)節(jié)點(diǎn) A，需要 A 和其兩個(gè)子節(jié)點(diǎn)比較大小，如果 A 不是最大的就需要調(diào)整位置，要把較大的那個(gè)子節(jié)點(diǎn)和 A 交換。

畫個(gè)圖看下就明白了：

至此，二叉堆的主要操作就講完了，一點(diǎn)都不難吧，代碼加起來(lái)也就十行。明白了sink和swim的行為，下面就可以實(shí)現(xiàn)優(yōu)先級(jí)隊(duì)列了。

四、實(shí)現(xiàn) delMax 和 insert

這兩個(gè)方法就是建立在swim和sink上的。

insert方法先把要插入的元素添加到堆底的最后，然后讓其上浮到正確位置。

public void insert(Key e) {
    N++;
    // 先把新元素加到最后
    pq[N] = e;
    // 然后讓它上浮到正確的位置
    swim(N);
}

delMax方法先把堆頂元素 A 和堆底最后的元素 B 對(duì)調(diào)，然后刪除 A，最后讓 B 下沉到正確位置。

至此，一個(gè)優(yōu)先級(jí)隊(duì)列就實(shí)現(xiàn)了，插入和刪除元素的時(shí)間復(fù)雜度為 O(logK)，K為當(dāng)前二叉堆（優(yōu)先級(jí)隊(duì)列）中的元素總數(shù)。因?yàn)槲覀儠r(shí)間復(fù)雜度主要花費(fèi)在sink或者swim上，而不管上浮還是下沉，最多也就樹（堆）的高度，也就是 log 級(jí)別。

五、最后總結(jié)

二叉堆就是一種完全二叉樹，所以適合存儲(chǔ)在數(shù)組中，而且二叉堆擁有一些特殊性質(zhì)。

二叉堆的操作很簡(jiǎn)單，主要就是上浮和下沉，來(lái)維護(hù)堆的性質(zhì)（堆有序），核心代碼也就十行。

優(yōu)先級(jí)隊(duì)列是基于二叉堆實(shí)現(xiàn)的，主要操作是插入和刪除。插入是先插到最后，然后上浮到正確位置；刪除是把第一個(gè)元素 pq[1]（最值）調(diào)換到最后再刪除，然后把新的 pq[1] 下沉到正確位置。核心代碼也就十行。

也許這就是數(shù)據(jù)結(jié)構(gòu)的威力，簡(jiǎn)單的操作就能實(shí)現(xiàn)巧妙的功能，真心佩服發(fā)明二叉堆算法的人！