算法流程：?

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

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

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

我們插入一個(gè)85，當(dāng)85還沒來的時(shí)候，此時(shí)的堆是一個(gè)合法的大堆，所有的節(jié)點(diǎn)都大于等于子樹中所有節(jié)點(diǎn)，85到來的時(shí)候，我會(huì)拿它和它的父節(jié)點(diǎn)作比較，如果它小于父結(jié)點(diǎn)，比如3，那就不用調(diào)整，因?yàn)楫?dāng)前節(jié)點(diǎn)小于父節(jié)點(diǎn)，也肯定小于父節(jié)點(diǎn)的父結(jié)點(diǎn)，因?yàn)檫@是一個(gè)堆結(jié)構(gòu)，只要他小于父結(jié)點(diǎn)，他肯定小于沿著這個(gè)節(jié)點(diǎn)向上的所有節(jié)點(diǎn)，因此在3到來的時(shí)候它還是合法的；但是當(dāng)85到來的時(shí)候，85的值大于22，因此我會(huì)讓較大的值往上轉(zhuǎn)移，轉(zhuǎn)移完之后下面的堆就合法了，85是大于22的，因?yàn)?2大于左子樹數(shù)，所以我把較大的值挪下來之后，85肯定大于下面兩顆子樹里面所有的節(jié)點(diǎn)，因此85轉(zhuǎn)移下來之后，下面的小樹就合法了

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

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

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

向上調(diào)整算法時(shí)間復(fù)雜度

最壞情況下節(jié)點(diǎn)會(huì)從最后一層開始轉(zhuǎn)移上一層，再轉(zhuǎn)移上一層，所以他向上轉(zhuǎn)移的次數(shù)跟樹的高度是一樣的，在我們學(xué)習(xí)完全二叉樹性質(zhì)的時(shí)候，當(dāng)整棵樹節(jié)點(diǎn)個(gè)數(shù)為N的話，它的樹的高度是loh以2為底N +1的對(duì)數(shù)，時(shí)間復(fù)雜度就是O（logN）

代碼實(shí)現(xiàn)：

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

• 這個(gè)向上調(diào)整算法是為建堆服務(wù)的，對(duì)我們建完堆之后再來測(cè)試