用Heap 實作Priority Queue - 朝陽科技大學

用Heap 實作Priority Queue. Priority Queue. 面對同性質的許多筆記錄時(例如數百位申請獎助學金的學生的學籍資料), 我們會需要一個可以收納這些記錄的大型資料結構。

light dark 我的部落格: 人權 玩具 快速跳到: 社群活動 本層目錄 上層目錄 此頁@朝陽 此頁@資管 English 用Heap實作PriorityQueue PriorityQueue 面對同性質的許多筆記錄時(例如數百位申請獎助學金的學生的學籍資料), 我們會需要一個可以收納這些記錄的大型資料結構。

用c++的術語來說, 這類具收納功能的資料結構都叫做container。

例如陣列, linkedlist,集合,...等等都是containers。

有時候我們最常做的動作,是從一個container當中固定取出其中 「優先順序最高」少數幾筆資料 (例如根據複雜公式計算出來的獎助優先順序)。

當然我們也可能需要新增資料,甚至可能改變其中某一筆資料的 「優先順序」。

一個container(姑且稱之為PQ),除收納功能以外, 如果還提供以下功能,就稱為一個priorityqueue: insert:新增一筆記錄進入PQ。

remove:傳回「優先順序」最高的那一筆記錄,並將它從 PQ當中刪除。

change:改變PQ裡面一筆記錄的「優先順序」。

is_empty:查詢PQ裡面是否已清空,沒有任何記錄。

繼續以c++的術語來說,priorityqueue其實是一個abstract class--它不像二元樹或doublylinkedlist 等等那麼清楚地有明確的結構,它只是一個抽象的介面 interface。

有許多不同的實際資料結構, 都可以拿來提供上述功能,也就是說,我們想實作implement 出一個priorityqueue,其實有許多資料結構可以用,例如unsortedarray, sortedarray,unsortedlinkedlist,sortedlinkedlist。

請仔細思考用每一種資料結構實作時,每個功能該如何實作; 各需要多少時間。

然後與下表對一下答案。

insert remove change is_empty search unsortedarray O(1) O(n) srch+O(1) O(1) O(n) sortedarray O(n) O(n) O(n) O(1) O(lgn) circularsortedarray O(n) O(1) O(n) O(1) O(lgn) unsortedlinkedlist O(1) O(n) srch+O(1) O(1) O(n) sortedlinkedlist O(n) O(1) O(n) O(1) O(n) 這裡的"srch+"表示搜尋的時間。

如果已知要改變優先順序的元素在那裡,srch=0;否則srch就是search 欄的時間。

circularsortedarray是sortedarray的改進版,有點像是circular queue。

要把它的search寫成O(lgn),需要一些功夫。

PriorityQueue可以拿來排序。

用下面這個演算法: voidpqsort(){ for(i=0;i0;--i)downheap(i)的順序正好可以達成這個效果。

耗時多少?最開始的n/2個元素各耗時1;其次的n/4個元素各耗時2; 再來的n/8個元素各耗時3...共耗時O(n) 「最小元素放root」的heap,叫做min-heap;「最大元素放root」的 heap,叫做max-heap。

如上述,如果pqsort()當中所用的資料結構是heap, 那麼這個排序演算法就叫做heapsort。

如果我們的heap 主要只是為了拿來排序,那麼不如改用max-heap。

Heap建立好之後, 最大元素正好在root(陣列的第一個元素),把它和最後一個元素對調,想像 heap縮小一格,而排序完畢的陣列正好從尾巴開始逐漸出現。

這樣heapsort 就變成是in-place了。

請在命令列下執行:perlHeap.pm 觀察它的輸出。

首先是建立heap的過程,由下而上,每完成一層的 downheap,就將整個heap列印一次。

其次是隨意新增幾個元素。

最後將所有元素逐一刪除。

你可以修改程式下方$data 變數的初始值,甚至可以改成用亂數產生,用不同的資料跑跑看。

本頁最新版網址: https://www.cyut.edu.tw/~ckhung/b/al/heap.php; 您所看到的版本:February14201202:32:24. 作者:朝陽科技大學資訊管理系洪朝貴 寶貝你我的地球,請 減少列印,多用背面,丟棄時做垃圾分類。

本文件以 CreativeCommonsAttribution-ShareAlikeLicense 或以 FreeDocumentLicense方式公開授權大眾自由複製/修改/散佈。