heapify()
前面兩篇文章介紹了什么是堆以及堆的兩個基本操作，但其實呢，堆還有一個大名鼎鼎的非常重要的操作，就是 heapify() 了，它是一個很神奇的操作，
可以用 O(n) 的時間把一個亂序的陣列變成一個 heap，
但是呢，heapify() 并不是一個 public API，看：
所以我們沒有辦法直接使用，
唯一使用 heapify() 的方式呢，就是使用
PriorityQueue(Collection<? extends E> c)
這個 constructor 的時候，人家會自動呼叫 heapify() 這個操作，
那具體是怎么做的呢？
哈哈原始碼已經暴露了：
從最后一個非葉子節點開始，從后往前做 siftDown().
因為葉子節點沒必要操作嘛，已經到了最下面了，還能和誰 swap？
舉個例子：
我們想把這個陣列進行 heapify() 操作，想把它變成一個最小堆，拿到它的最小值，
那就要從 3 開始，對 3，7，5進行 siftDown().
Step 1.
尷尬 ??，3 并不用交換，因為以它為頂點的這棵小樹已經滿足了堆序性，
Step 2.
7 比它的兩個孩子都要大，所以和較小的那個交換一下，
交換完成后；
Step 3.
最后一個要處理的就是 5 了，那這里 5 比它的兩個孩子都要大，所以也和較小的那個交換一下，
換完之后結果如下，注意并沒有滿足堆序性，因為 4 還比 5 小呢，
所以接著和 4 換，結果如下：
這樣整個 heapify() 的程序就完成了，
好了難點來了，為什么時間復雜度是 O(n) 的呢？
怎么計算這個時間復雜度呢？
其實我們在這個程序里做的操作無非就是交換交換，
那到底交換了多少次呢？
沒錯，交換了多少次，時間復雜度就是多少，
那我們可以看出來，其實同一層的節點最多交換的次數都是相同的，
那么這個總的交換次數 = 每層的節點數 * 每個節點最多交換的次數
這里設 k 為層數，那么這個例子里 k=3.
每層的節點數是從上到下以指數增長：
$$\ce{1, 2, 4, ..., 2^{k-1}}$$
每個節點交換的次數，
從下往上就是：
$$ 0, 1, ..., k-2, k-1 $$
那么總的交換次數 S(k) 就是兩者相乘再相加：
$$S(k) = \left(2^{0} *(k-1) + 2^{1} *(k-2) + ... + 2^{k-2} *1 \right)$$
這是一個等比等引數列，標準的求和方式就是錯位相減法，
那么
$$2S(k) = \left(2^{1} *(k-1) + 2^{2} *(k-2) + ... + 2^{k-1} *1 \right)$$
兩者相減得：
$$S(k) = \left(-2^{0} *(k-1) + 2^{1} + 2^{2} + ... + 2^{k-2} + 2^{k-1} \right)$$
化簡一下：
（不好意思我實在受不了這個編輯器了，，，
所以 heapify() 時間復雜度是 O(n).
以上就是堆的三大重要操作，最后一個 heapify() 雖然不能直接操作，但是堆排序中用到了這種思路，之前的「選擇排序」那篇文章里也提到了一些，感興趣的同學可以后臺回復「選擇排序」獲得文章～至于堆排序的具體實作和應用，以及為什么實際生產中并不愛用它，我們之后再講，
如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！
我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，云自習室里不見不散！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/179763.html
標籤：其他
上一篇：導航（持續更新）
下一篇：導航（持續更新）