noip普及講座8-堆及其應(yīng)用-在線瀏覽
2024-11-17 05:39本頁面
【正文】 ,第十二頁，共三十九頁。,Put操作,procedure put(x:longint)。 begin len:=len+1。 son:=len。 heap[son div 2]:=heap[son]。 son:=son div 2。 end。,Put操作,void put(int x) { int fa,son,tmp。 heap[len]=x。 while (son!=1 } },第十五頁，共三十九頁。,Get操作,5,7,5,4,6,1,4,3,2,1,heap,第十七頁，共三十九頁。,Get操作,5,7,5,4,6,4,3,2,1,heap,pa,第十九頁，共三十九頁。,function get:longint。 begin get:=heap[1]。 len:=len1。 while pa*2len) or (heap[pa*2]heap[son] then begin tmp:=heap[pa]。 heap[son]:=tmp。 end else break。 end。,int get() { int p=heap[1],pa=1,son,tmp。 len。 heap[pa]=heap[son]。 pa=son。 } return p。,建立堆,方法一：對(duì)數(shù)組中的每個(gè)數(shù)依次進(jìn)行插入操作。 for i:=1 to n do put(a[i])。ia[i]。i=n。 方法二：直接對(duì)數(shù)組a進(jìn)行調(diào)整，從a[n div 2]開始向下調(diào)整成堆，然后對(duì)a[n div 21]調(diào)整,直至a[1]。,堆的應(yīng)用,例堆排序 假設(shè)n個(gè)隨機(jī)整數(shù)存放在A[1n]中，我們可以利用堆將它們從小到大進(jìn)行排序，這種排序方法，稱為“堆排序”。 Pascal: for i:=1 to n do writeln(get)。i=n。,第二十四頁，共三十九頁。因?yàn)槠溥\(yùn)算的時(shí)間主要消耗在建立初始堆和調(diào)整過程中，堆排序的時(shí)間復(fù)雜度為O（nlog2n），而且堆排序只需一個(gè)供交換用的輔助單元空間，是一種不穩(wěn)定的排序方法。,堆的應(yīng)用,例丑數(shù)（H數(shù)） 丑數(shù)是指素因子都在集合{2，3，5，7}的數(shù)，求第n大的丑數(shù)(n6000) ，第一個(gè)丑數(shù)是1。 ?,第二十六頁，共三十九頁。 heap[1]:=1。 i:=0。 k2:=0。
物理相關(guān)推薦
鄂ICP備17016276號(hào)-1