堆簡述
堆（heap）的結(jié)構(gòu)是一個完全二叉樹的結(jié)構(gòu)。
堆分大根堆和小根堆止潮。如果一個二叉樹它即不是大根堆，也不是小根堆钞楼，那它不是堆喇闸。
大根堆：每一個根節(jié)點，都大于它的兩個子節(jié)點询件。
小根堆：每一個根節(jié)點燃乍，都小于它的兩個子節(jié)點。
注意宛琅，大根堆和小根堆并不能保證在不同分支上它們的大小關(guān)系有規(guī)律刻蟹。
樹的高度為 logN（可以發(fā)現(xiàn)每一層満時它在此層 i 的元素個數(shù)為 2^i）。
完全二叉樹夯秃，每個節(jié)點最多有兩節(jié)點座咆，完全二叉樹中，每一層或是満的仓洼，或是從左到右依次變満的狀態(tài)介陶。
參考：https://visualgo.net/en/heap
堆的實現(xiàn)
堆可以用數(shù)組實現(xiàn)。
[0, 1, 2, 3, 4, 5] 可依次從上到下色建，從左到右填入完全二叉樹中哺呜。
則數(shù)組下標(biāo)中 i 位置，它尋找節(jié)點的關(guān)系為
- 父節(jié)點：(i - 1) / 2箕戳；
- 左子節(jié)點：2 * i + 1某残；
- 右子節(jié)點： 2 * i + 2；
有時陵吸，常常為了方便玻墅，將數(shù)組下標(biāo) 0 的元素棄而不，所以當(dāng) i' 從 1 開始時壮虫，則對應(yīng)關(guān)系為：
- 父節(jié)點：i' / 2澳厢；
- 左子節(jié)點： 2 * i'环础；
- 右子節(jié)點： 2 * i' + 1；
不用 0 元素剩拢，是因為在找下標(biāo)時很容易用移位（>> 或 <<）的方式找到關(guān)聯(lián)的下標(biāo)位置线得。
而對 0 移位操作得到的結(jié)果始終為 0，不方便找尋相關(guān)節(jié)點的下標(biāo)徐伐。
2 * i + 1 = i << 1 | 1
維護(hù)大根堆
小根堆與大根堆規(guī)則一樣贯钩，不再綴述。
請參考 https://visualgo.net/en/heap 中的演示办素。
添加過程
所以角雷，構(gòu)建大根堆的過程：
- 將此數(shù)放在堆的最后一個位置
- 將此數(shù)與其父節(jié)點比較，大則交換摸屠，小則停止
- 重復(fù)第二步驟谓罗，直到此數(shù)找到合適的位置
因為添加每一個元素它移動的步數(shù)正好為二叉樹的高度，所以每一步的復(fù)雜度 logN季二。
移除堆中的最大值后調(diào)整以維持大根堆（heapify）
方法：將最后一個值放到移除的位置（原來最大值的位置）檩咱，讓最小值向下沉，直到找到合適位置胯舷。
步驟：
- 將最末值 Z 放入最大根位置（樹頂）刻蚯；
- 堆空間大小（heapSize）減 1桑嘶；（用一個變量來維護(hù)的堆的大写缎凇）
- 將 Z 分別與其子節(jié)點比較，若 Z 小逃顶，則與大者交換讨便，若 Z 大于所有的子節(jié)點或無子節(jié)點則停止；
- 重復(fù)上一步過程以政，直到 Z 停止移動霸褒。
堆排序
堆排序是指，給定一個數(shù)組盈蛮，然后將此數(shù)組構(gòu)建成堆（這里為大根堆）废菱，然后將它排序成從小到大的順序。
方法一
有了上方維護(hù)大根堆過程的原理后抖誉，這個方法就很好理解了：
- 將數(shù)組構(gòu)建成大根堆殊轴；（
O(N*logN)） - 將堆的最大根與最末值進(jìn)行交換（最大值放到最末）；
- heapSize - 1 （已放到最后的最大值不再比較）袒炉；
- 將此時的堆空間進(jìn)行 heapify旁理；（
O(logN)） - 重復(fù)上述 2 - 4 步驟，直到 heapSize 等于 1我磁；（
O(N)）
此時整個數(shù)組就變成了已排序的了韧拒。
時間復(fù)雜度 O(N*logN) + O(logN) * O(N) => O(N*logN)
方法二
在方法一上進(jìn)行優(yōu)化淹接。優(yōu)化點是在數(shù)組構(gòu)建成大根堆的過程上（也就是方法一的步驟 1 中）。
數(shù)組構(gòu)建為大根堆優(yōu)化版思路總述：將數(shù)組看成一個完全二叉樹叛溢，從下往上開始，保證每一個子樹為大根堆（小值下沉的方法）劲适，最后得到一個大根堆楷掉。
步驟：
- 二叉樹最底層每一個元素均為一個大根堆
- 二叉樹倒數(shù)第二層每一個元素與其子元素比較，利用上方的小值下沉的方法霞势，使其每個元素與其子節(jié)點為大根堆
- 重復(fù)以上步驟烹植，判斷倒數(shù)第 k 層，使其每個元素作為父節(jié)點成為大根堆愕贡，直到 k 表示為頂層草雕。
這其中，不用判斷最后一層固以，只需要用下標(biāo)從 N-1 變到 0 即可墩虹。
這種方法將構(gòu)建大根堆的時間復(fù)雜度優(yōu)化為 O(N)。
小結(jié)：構(gòu)建堆憨琳，自上而下的方法時間復(fù)雜度為 O(N*logN)诫钓，自下而上的方法時間復(fù)雜度為 O(N)。
面試題：幾乎有序的數(shù)組的排序
幾乎有序是指篙螟，若將數(shù)組排好順序菌湃，每個元素移動的位置不超過一個常數(shù) k。
思路遍略，這個題就可以用堆（具體是小根堆）來做惧所。根據(jù)題意，要得到的排序結(jié)果在 i 位置上的數(shù)一定是在 i - k 到 i + k 之間绪杏，所以有 2k + 1 個可能下愈。但從第一個元素開始放入正確的值時，后面每一個位置的可選項只有 k + 1 個寞忿。所以堆的大小是 k + 1驰唬，每 k + 1 個數(shù)放滿小根堆后就可以確定第一個小值所在的位置。堆不滿而元素已放完時腔彰，從剩下堆中選即可叫编。
復(fù)雜度，O(N*logk)
