noip普及講座8-堆及其應(yīng)用(編輯修改稿)
2024-11-17 05:39 本頁面
【文章內(nèi)容簡介】 立堆,方法一：對數(shù)組中的每個數(shù)依次進(jìn)行插入操作。 Pascal: for i:=1 to n do read(a[i])。 for i:=1 to n do put(a[i])。 C++: for (int i=1。ia[i]。 for (int i=1。i=n。i++) put(a[i])。 方法二：直接對數(shù)組a進(jìn)行調(diào)整，從a[n div 2]開始向下調(diào)整成堆，然后對a[n div 21]調(diào)整,直至a[1]。,第二十三頁，共三十九頁。,堆的應(yīng)用,例堆排序 假設(shè)n個隨機(jī)整數(shù)存放在A[1n]中，我們可以利用堆將它們從小到大進(jìn)行排序，這種排序方法，稱為“堆排序”。 【問題分析】 (1) 建立小根堆 (2) 取出根結(jié)點(diǎn)并調(diào)整堆：將根結(jié)點(diǎn)輸出，并與小根堆的最后一個結(jié)點(diǎn)交換，再從上到下進(jìn)行調(diào)整，使其仍為小根堆，重復(fù)(2)操作，最后輸出數(shù)組。 Pascal: for i:=1 to n do writeln(get)。 C++: for (int i=1。i=n。i++) coutget()endl。,第二十四頁，共三十九頁。,堆的應(yīng)用,【小結(jié)】 堆排序在數(shù)據(jù)較少時并不值得提倡，但數(shù)據(jù)量很大時，效率就會很高。因?yàn)槠溥\(yùn)算的時間主要消耗在建立初始堆和調(diào)整過程中，堆排序的時間復(fù)雜度為O（nlog2n），而且堆排序只需一個供交換用的輔助單元空間，是一種不穩(wěn)定的排序方法。,第二十五頁，共三十九頁。,堆的應(yīng)用,例丑數(shù)（H數(shù)） 丑數(shù)是指素因子都在集合{2，3，5，7}的數(shù)，求第n大的丑數(shù)(n6000) ，第一個丑數(shù)是1。 【問題分析】 ?窮舉顯然不行，嘗試用“構(gòu)造法”不斷生成丑數(shù)； ?構(gòu)造的基本思想：5個線性表，時間復(fù)雜度O(n2) ?其中的關(guān)鍵操作：取最小結(jié)點(diǎn)、插入新結(jié)點(diǎn)； ?可以利用二叉堆(小根堆)的基本操作。 ?,第二十六頁，共三十九頁。,堆的應(yīng)用,readln(n)。 heap[1]:=1。 len:=1。 i:=0。 k1:=0。 k2:=0。 while ik2 then begin i:=i+1。 put(k2*2)。 put(k2*3)。 put(k2*5)。 put(k2*7)。 end。 end。 writeln(k2)。,判斷前后兩次取出的數(shù)是否一樣,把生成的新數(shù)加入到堆中,第二十
物理相關(guān)推薦
鄂ICP備17016276號-1