A 講解:
堆是一種資料結構 具有以下特性:
● 堆中某個節點值總是不大於或不小於其父節點值
● 必定是一棵完全樹
而在這邊只簡單介紹以下三種相關問題
● 最大堆 (max heap)
● 最小堆 (min heap)
● 堆排序 (Heapsort)
值得注意一點 就是在C語言中 實做堆時一般皆是用一維陣列解決
另外遇到"優先隊列"(Priority Queue)問題 就是用堆(Heap)來處理
先從最大最小堆開始說起吧
他們兩個都有以下特性:
● 父節點的鍵值總是大於或等於(小於或等於)任何一個子結點的鍵值
● 一定是一個"二元"完全樹(complete binary tree) -- 故最大最小堆是一種二叉堆
常用的操作有以下兩種:
● 插入 (Insert)
● 刪除 (Delete)
最大最小堆圖例:
max heap: min heap:
55 2
/ \ / \
28 33 16 33
/ \ / / \
11 7 19 28 34
{55, 28, 33, 11, 7, 19} {2, 16, 33, 28, 34}
在建構堆的演算法講解方面 就以最大堆為例 而最小堆只要在判斷地方反向操作就行
首先是"插入" (Insert)
因為是完全樹 故新元素的插入必定是由左而右 也是因為這個特性 所以堆適合用陣列實做
接著 判斷新節點是否"大於"父節點 如果大於則交換 持續換到比父節點小或已經成為"根"(root)為止
第二個是"刪除" (Delete)
因為是完全樹 故刪除"根"後 必須用最後一個元素(最下層且最右邊)取代
然後和自己兩個子節點比較 和較大的換 持續直至兩個子節點都比自己小
以上就是最大最小堆的說明
接著來介紹堆排序吧:
關於程式碼可以參考這篇http://codelearner.pixnet.net/blog/post/131268205
基本上 就是先建構一個最大堆
建立好後 將第一個元素(最大) 和最後一個元素交換 此步驟即為"delete"
接著 把最後一個元素視為"已排序" 排除在堆之外
而前面的元素仍然在最大堆之中
持續操作直至堆的大小為"1"
虛擬碼:
for(i = n; i >= 2; i--){
swap(A[1], A[i]);
heapify(A[1], A[i - 1]);
}
B 範例例題如下:
建一個 min heap
"Insert XX" 指令即為插入
"Delete" 指令即為刪除
每一個插入指令都要同時印出陣列內所有元素
每一個刪除指令都要同時印出刪除之元素
當沒有東西可以刪除時 要顯示 "Empty"
EX:
Input:
Insert 22
Insert 17
Insert 69
Insert 3
Insert 58
Delete
Delete
Delete
Delete
Delete
Delete
Output:
22
17 22
17 22 69
3 17 69 22
3 17 69 22 58
3
17
22
58
69
Empty
C 範例程式碼:
D 相關問題:
UVA 10954 http://codelearner.pixnet.net/blog/post/131317471
留言列表
