資源簡介
優先隊列由一個基于堆的完全二叉樹表示，存儲于數組pq[1...N]中，pq[0]沒有使用。在insert()中，我們將N加一并把新元素添加在數組最后，然后用swim()恢復堆的秩序。在delMax()中，我們從pq[1]中得到需要返回的元素，然后將pq[N]移動到pq[1]，將N減一并用sink()恢復堆的秩序。同時我們還將不再使用的pq[N 1]設為null，以便系統回收它所占用的空間。
命題：對于一個含有N個元素的基于堆的優先隊列，插入元素操作只需不超過（lgN 1）次比較，刪除最大元素的操作需要不超過2lgN次比較。
證明：由上一個命題可知，兩種操作都需要在根結點和堆底之間移動元素，而路徑的長度不超過lgN。對于路徑上的每個結點，刪除最大元素需要兩次比較（除了堆底元素），一次用來找出較大的子結點，一次用來確定該子結點是否需要上浮。
對于需要大量混雜的插入和刪除最大元素操作的典型應用來說，上面的命題意味著一個重要的性能突破。使用有序或是無序數組的優先隊列的初級實現總是需要線性時間來完成其中一種操作，但基于堆的實現則能夠保證在對數時間內完成它們。這種差別使得我們能夠解決以前無法解決的問題。
堆上的優先隊列操作如下圖
代碼片段和文件信息
package?com.huazhou;
import?android.app.Application;
import?android.test.ApplicationTestCase;
/**
?*?Testing?Fundamentals
?*/
public?class?ApplicationTest?extends?ApplicationTestCase?{
????public?ApplicationTest（）?{
????????super（Application.class）;
????}
} ?屬性????????????大小?????日期????時間???名稱
-----------?---------??----------?-----??----
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\
?????文件??????????13??2015-12-15?07:21??Algorithms-master\README.md
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\TXTFiles\
?????文件??????????32??2015-12-15?07:21??Algorithms-master\TXTFiles\shell.txt
?????文件??????726569??2015-12-15?07:21??Algorithms-master\TXTFiles\tale.txt
?????文件??????????22??2015-12-15?07:21??Algorithms-master\TXTFiles\tiny.txt
?????文件?????????496??2015-12-15?07:21??Algorithms-master\TXTFiles\tinyBatch.txt
?????文件??????????36??2015-12-15?07:21??Algorithms-master\TXTFiles\tinyCG.txt
?????文件?????????138??2015-12-15?07:21??Algorithms-master\TXTFiles\tinyDG.txt
?????文件??????????63??2015-12-15?07:21??Algorithms-master\TXTFiles\tinyG.txt
?????文件?????????277??2015-12-15?07:21??Algorithms-master\TXTFiles\tinyTale.txt
?????文件?????????141??2015-12-15?07:21??Algorithms-master\TXTFiles\words3.txt
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\
?????文件???????????7??2015-12-15?07:21??Algorithms-master\app\.gitignore
?????文件?????????578??2015-12-15?07:21??Algorithms-master\app\build.gradle
?????文件?????????653??2015-12-15?07:21??Algorithms-master\app\proguard-rules.pro
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\androidTest\
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\androidTest\java\
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\androidTest\java\com\
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\androidTest\java\com\huazhou\
?????文件?????????342??2015-12-15?07:21??Algorithms-master\app\src\androidTest\java\com\huazhou\ApplicationTest.java
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\main\
?????文件?????????279??2015-12-15?07:21??Algorithms-master\app\src\main\AndroidManifest.xm
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\main\res\
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-hdpi\
?????文件????????3418??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-hdpi\ic_launcher.png
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-mdpi\
?????文件????????2206??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-mdpi\ic_launcher.png
?????目錄???????????0??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-xhdpi\
?????文件????????4842??2015-12-15?07:21??Algorithms-master\app\src\main\res\mipmap-xhdpi\ic_launcher.png
............此處省略97個文件信息
- 上一篇：C# 多維數據庫 數據挖掘
- 下一篇：C# 通訊錄源碼實現了增刪改功能（含數據庫）
評論
共有 條評論