基本操作
任何一個資料結構，無非就是增刪改查四大類：
| 功能 | 方法 | 時間復雜度 |
|---|---|---|
| 增 | offer(E e) | O(logn) |
| 刪 | poll() | O(logn) |
| 改 | 無直接的 API | 刪 + 增 |
| 查 | peek() | O(1) |
這里 peek() 的時間復雜度很好理解，因為堆的用途就是能夠快速的拿到一組資料里的最大/最小值，所以這一步的時間復雜度一定是 O(1) 的，這就是堆的意義所在，
那么我們具體來看 offer(E e) 和 poll() 的程序，
offer(E e)
比如我們新加一個 0 到剛才這個最小堆里面：
那很明顯，0 是要放在最上面的，可是，直接放上去就不是一棵完全二叉樹了啊，，
所以說，
我們先保證加了元素之后這棵樹還是一棵完全二叉樹， 然后再通過 swap 的方式進行微調，來滿足堆序性，
這樣就保證滿足了堆的兩個特點，也就是保證了加入新元素之后它還是個堆，
那具體怎么做呢：
Step 1.
先把 0 放在最后接上，別一上來就想著上位；
OK！總算先上岸了，然后我們再一步步往上走，
這里「能否往上走」的標準在于：
是否滿足堆序性，
也就是說，現在 5 和 0 之間不滿足堆序性，那么交換位置，換到直到滿足堆序性為止，
這里對于最小堆來說的堆序性，就是小的數要在上面，
Step 2. 與 5 交換
此時 0 和 3 不滿足堆序性了，那么再交換，
Step 3. 與 3 交換
還不行，0 還比 1 小，所以繼續換，
Step 4. 與 1 交換
OK！這樣就換好了，一個新的堆誕生了～
總結一下這個方法：
先把新元素加入陣列的末尾，再通過不斷比較與 parent 的值的大小，決定是否交換，直到滿足堆序性為止，
這個程序就是 siftUp()，原始碼如下：
時間復雜度
這里不難發現，其實我們只交換了一條支路上的元素，
也就是最多交換 O(height) 次，
那么對于完全二叉樹來說，除了最后一層都是滿的，O(height) = O(logn)，
所以 offer(E e) 的時間復雜度就是 O(logn) 啦，
poll()
poll() 就是把最頂端的元素拿走，
對了，沒有辦法拿走中間的元素，畢竟要 VIP 先出去，小弟才能出去，
那么最頂端元素拿走后，這個位置就空了：
我們還是先來滿足堆序性，因為比較容易滿足嘛，直接從最后面拿一個來補上就好了，先放個傀儡上來，
Step1. 末尾元素上位
這樣一來，堆序性又不滿足了，開始交換元素，
那 8 比 7 和 3 都大，應該和誰交換呢？
假設與 7 交換，那么 7 還是比 3 大，還得 7 和 3 換，麻煩，
所以是與左右孩子中較小的那個交換，
Step 2. 與 3 交換
下去之后，還比 5 和 4 大，那再和 4 換一下，
Step 3. 與 4 交換
OK！這樣這棵樹總算是穩定了，
總結一下這個方法：
先把陣列的末位元素加到頂端，再通過不斷比較與左右孩子的值的大小，決定是否交換，直到滿足堆序性為止，
這個程序就是 siftDown()，原始碼如下：
時間復雜度
同樣道理，也只交換了一條支路上的元素，也就是最多交換 O(height) 次，
所以 offer(E e) 的時間復雜度就是 O(logn) 啦，
那以上就是有關堆的基本操作啦！對于堆，還有一個比較特別的操作，就是 heapify()，這是一個很神奇的操作，至于神奇在何處、為什么它能做到、它是怎么做到的，我們下一篇文章再說～
如果你喜歡這篇文章，記得給我點贊留言哦～你們的支持和認可，就是我創作的最大動力，我們下篇文章見！
我是小齊，紐約程式媛，終生學習者，每天晚上 9 點，云自習室里不見不散！
更多干貨文章見我的 Github: https://github.com/xiaoqi6666/NYCSDE
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/161256.html
標籤：其他
上一篇：深入理解cookie和session，這一篇就夠了（建議收藏）
下一篇：順時針列印矩陣