算法流程：?

1. 與?結點的權值作?較，如果?它?，就與?親交換；?
2. 交換完之后，重復 1 操作，直到??親?，或者換到根節(jié)點的位置

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

這里為什么插入85完后合法？

我們插入一個85，當85還沒來的時候，此時的堆是一個合法的大堆，所有的節(jié)點都大于等于子樹中所有節(jié)點，85到來的時候，我會拿它和它的父節(jié)點作比較，如果它小于父結點，比如3，那就不用調整，因為當前節(jié)點小于父節(jié)點，也肯定小于父節(jié)點的父結點，因為這是一個堆結構，只要他小于父結點，他肯定小于沿著這個節(jié)點向上的所有節(jié)點，因此在3到來的時候它還是合法的；但是當85到來的時候，85的值大于22，因此我會讓較大的值往上轉移，轉移完之后下面的堆就合法了，85是大于22的，因為22大于左子樹數，所以我把較大的值挪下來之后，85肯定大于下面兩顆子樹里面所有的節(jié)點，因此85轉移下來之后，下面的小樹就合法了

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ??

但是上面的我們還不確定，所以我們要繼續(xù)拿85和上面的點做比較，當我們發(fā)現85比39還大的時候就繼續(xù)轉移，轉移完之后下面的子樹依舊是合法的，因為39沒轉移之前是大于它的左子樹和右子樹里面所有的點，所以當我把39轉移到下面的時候，他依舊是大于20和22這兩個點的，把39轉移到下面的子樹是不受影響的，但是當我把85轉移到上面的紅圈中的子樹就合法了，原因就是剛剛85是比39大的，85轉移到上面之后，85肯定是大于剛剛左子樹里面所有的節(jié)點，以及剛剛右子樹里面所有的節(jié)點，因為39放在這里就合法，那我把85放在這里也是合法的，因此當我把85轉移到上面的時候，整顆子樹就變得合法了，每次向上轉移，他都會讓一顆小子樹合法，繼續(xù)向上轉移，又會讓一顆小子樹合法，此時我們發(fā)現85比99小，左邊的子樹就合法了，右邊的子樹本身就是合法的，因為85到來的時候并不會影響右子樹，85向上調整的時候，他會讓一個小子樹再讓一顆小子樹變得合法，因此整個指數就變得合法了，所以這里為什么合法，就是一個簡單比大小的過程，一直讓大的元素向上再向上，上到不能再上的時候整個數就合法了，這就是堆的第一個核心操作向上調整算法，如果是小堆的話，就讓小元素向上走

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

向上調整算法時間復雜度

最壞情況下節(jié)點會從最后一層開始轉移上一層，再轉移上一層，所以他向上轉移的次數跟樹的高度是一樣的，在我們學習完全二叉樹性質的時候，當整棵樹節(jié)點個數為N的話，它的樹的高度是loh以2為底N +1的對數，時間復雜度就是O（logN）

代碼實現：

const int N = 1e6 + 10;int n;
int heap[N];//向上調整算法
void up(int child) //每次和父親做比較
{int parent = child / 2;//父節(jié)點存在且當前結點值大于父節(jié)點的權值while (parent >= 1 && heap[child] > heap[parent]){swap(heap[child], heap[parent]);child = parent;parent = child / 2;}
}

• 這個向上調整算法是為建堆服務的，對我們建完堆之后再來測試