noip普及講座8-堆及其應用-全文預覽
【正文】 小根堆的最后一個結(jié)點交換，再從上到下進行調(diào)整，使其仍為小根堆，重復(2)操作，最后輸出數(shù)組。i++) put(a[i])。 C++: for (int i=1。 },第二十二頁，共三十九頁。 heap[son]=tmp。 heap[1]=heap[len]。 end。 heap[pa]:=heap[son]。 heap[1]:=heap[len]。,Get操作,5,7,5,6,4,4,3,2,1,heap,pa,第二十頁，共三十九頁。,Get操作,5,7,5,4,6,1,4,3,2,1,heap,第十六頁，共三十九頁。 len++。 end。 while (son1) and (heap[son div 2]heap[son]) do begin temp:=heap[son div 2]。 var fa,son,tmp:longint。,Put操作,5,7,5,6,1,4,4,3,2,1,heap,son,第十一頁，共三十九頁。 方法是往堆尾加入一個結(jié)點，并通過從下往上的調(diào)整法，使其繼續(xù)保持堆的性質(zhì)； Get操作：即從堆中取出根結(jié)點。,堆的性質(zhì),二叉堆還具有這樣一個重要的性質(zhì)：對除根以外的每個結(jié)點i，A[parent(i)]≥A[i]，即所有結(jié)點的值都不得超過其父結(jié)點的值，稱為大根堆。樹中每個結(jié)點與數(shù)組中存放該結(jié)點中值的那個元素相對應。,預備知識,完全二叉樹： 如果一棵深度為K的二叉樹，1至K1層的結(jié)點都是滿的，即滿足2i1(1=i=k1),只有最下面的一層的結(jié)點數(shù)小于等于2k1，并且最下面一層的結(jié)點都集中在該層最左邊的若干位置，則此二叉樹稱為完全二叉樹。,堆的定義,01,堆的性質(zhì),02,堆的基本操作,03,堆的應用,04,Table of Contents,內(nèi)容大綱,第二頁，共三十九頁。,堆的定義,堆也稱二叉堆，結(jié)構(gòu)上是一種數(shù)組，本質(zhì)上是一棵完全二叉樹。,第六頁，共三十九頁。,堆的基本操作,使用堆的關(guān)鍵部分是兩個基本操作： Put操作：即往堆中加入一個結(jié)點。,Put操作,5,7,5,6,1,4,4,3,2,1,heap,第十頁，共三十九頁。,Put操作,procedure put(x:longint)。 son:=len。 son:=son div 2。,Put操作,vo
物理相關(guān)推薦
鄂ICP備17016276號-1