>[success] # 堆 ~~~ 1.堆 數據結構，也叫作二叉堆，是一種特殊的二叉樹 2.它能高效、快 速地找出最大值和最小值，常被應用于優先隊列 3.堆的定義： 3.1.它是一棵完全二叉樹，完全二叉樹要求，除了最后一層，其他層的節點個數都是滿的， 最后一層的節點都靠左排列 3.2.堆中的每個節點的值必須大于等于（或者小于等于）其子樹中每個節點的值。也可以說， 堆中每個節點的值都大于等于（或者小于等于）其左右子節點的值。對于每個節點的值都大于等于子樹 中每個節點值的堆，我們叫做'大頂堆'。對于每個節點的值都小于等于子樹中每個節點值的堆， 我們叫做'小頂堆'。 4.平均情況下，它的時間復雜度為 O(nlogn) ~~~  >[info] ## 堆的實現 ~~~ 1.首先堆是樹的一種，樹的實現有兩種，一種是'鏈式存儲法',需要更多的空間保存左右指針，一種是'順序存儲法' 在針對完全二叉樹的形式用數組的方式，這樣節省空間，'堆'的特殊性就是一個完全二叉樹，因此用數組的作為 存儲方式是最合適的 2.對應的數組關系 2.1 它的左側子節點的位置是 2 * index + 1（如果位置可用） 2.2.它的右側子節點的位置是 2 * index + 2（如果位置可用） 2.3.它的父節點位置是 index / 2 向上取整（如果位置可用）。 3.這里對二條做個說明，實際我們通過這些公式算的是，對應位置節點位置，舉個例子，如圖，左側節點依次是 [2,4,6] 右側 [3,5,7] ,帶入公式2*index +1 想知道左側樹第一個位置的結點在大數組什么位置的時候，此時index為0 帶入后等于1則左側第一個節點在大數組角標為0的位置 ~~~ * 如圖堆 和 數組存儲對應關系