注意：為了更好的學習了解，本文實作了MATLAB程式，本文圖示大部分是書籍的截圖，因為書籍中的圖示和解釋非常嚴謹、非常詳細、非常棒！
堆排序
目錄
一、引言
二、維護堆的性質
三、建堆
四、堆排序算法
五、優先隊列
六、參考文獻
一、引言
- 1. 什麼是堆？
如上圖所示，（二叉）堆是一個數組，它可以被看成一個近似的完全二叉樹，樹上的每一個節點對應數組中的一個元素。除了底層外，該樹是完全充滿的，而且是從左向右填充。
- 2. 二叉堆的兩種形式：最大堆、最小堆
最大堆：最大堆的性質是指除了根以外的所有結點i都要滿足：
，也就是說，某個結點的值至多與其父節點一樣大。是以，堆中的最大元素存放在根節點中；并且在任意一子樹中，該子樹所包含的所有結點的值都不大于該子樹根節點的值。
最小堆：最小堆的性質是指除了根以外的所有結點i都要滿足：
，也就是說，最小堆的組織方式跟最大堆的相反，最小堆中的最小元素放在根節點中。
- 3. 完全二叉樹？
如上圖所示，除了最後一層之外的其他每一層都被完全填充，并且所有結點都保持向左對齊。
- 4. 堆的應用？
堆的應用比較廣泛，概括一下主要用在以下幾個方面，記憶體管理、資料處理、系統中核心和驅動事件優先級管理等等。
二、維護堆的性質
- 1. 擷取父節點下标
function index = parent(i)
index = i/2;
end
- 2. 擷取左孩子下标
function index = left(i)
index = 2*i;
end
- 3. 擷取右孩子下标
function index = right(i)
index = 2*i + 1;
end
- 4. 維護最大堆性質
如上圖所示，實作代碼如下：
% 1. 最大堆性質維護，可以了解為修正為最大堆
function [A_t] = max_heapify(A, i, n)
l = left(i); % (1) 擷取左下标
r = right(i); % (2) 擷取右下标
if l <= n && A(l) > A(i) % (3) 判斷左孩子是否大于父節點
largest = l;
else
largest = i;
end
if r <= n && A(r) > A(largest) % (4) 判斷右節點是否大于父節點
largest = r;
end
if largest ~= i % (5) 如果子節點大于父節點則交換值
temp = A(i);
A(i) = A(largest);
A(largest) = temp;
A = max_heapify(A, largest, n);
end
A_t = A;
end
- 5. 維護最小堆性質
function [A_t] = min_heapify(A, i, n)
l = left(i); % (1) 擷取左下标
r = right(i); % (2) 擷取右下标
if l <= n && A(l) < A(i) % (3) 判斷左孩子結點是否大于父結點
largest = l;
else
largest = i;
end
if r <= n && A(r) < A(largest) % (4) 判斷右孩子結點是否大于父結點
largest = r;
end
if largest ~= i % (5) 如果有則交換值
temp = A(i);
A(i) = A(largest);
A(largest) = temp;
A = max_heapify(A, largest, n);
end
A_t = A;
end
三、建堆
- 1. 建立最大堆
如上圖，程式如下：
function [ Y ] = build_max_heap( A )
% 建立最大堆
[m, n] = size(A); % (1). 擷取堆數組的大小
for i = floor(n/2):-1:1 % (2). 自底向上的方法利用max_heapify轉換A為最大堆
A = max_heapify(A, i, n);
end
Y = A;
end
- 2. 建立最小堆
function [ Y ] = build_min_heap( A )
% 建立最小堆
[m, n] = size(A); % (1). 擷取堆數組的大小
for i = floor(n/2):-1:1 % (2). 自底向上的方法利用max_heapify轉換A為最小堆
A = max_heapify(A, i, n);
end
Y = A;
end
四、堆排序算法
function [A_t] = heap_sort(A)
A = build_max_heap(A); % (1). 建立最大堆
[m,n] = size(A);
for i = n:-1:2 % (2). 重複調用max_heapify函數，構造新的最大堆
temp = A(1);
A(1) = A(i);
A(i) = temp;
n = n - 1;
A = max_heapify(A,1,n);
end
A_t = A;
end
五、優先隊列
優先隊列是一種用來維護由一組元素構成的集合S的資料結構，其中的每一個元素都有一個相關的值，稱為關鍵字（key）；普通的隊列是一種先進先出的資料結構，元素在隊列尾追加，而從隊列頭删除。在優先隊列中，元素被賦予優先級。當通路元素時，具有最高優先級的元素最先删除。優先隊列具有最進階先出 （first in, largest out）的行為特征。通常采用堆資料結構來實作。
優先隊列主要應用在任務和事件的排程上（優先級）。
- 1. 插入元素
function [A_t] = max_heap_insert(A, key)
% 把元素插入到集合A中
[m,n] = size(A);
A(n) = -10000;
A_t = heap_increase_key(A, n, key);
end
- 2. 檢索具有最大鍵字的元素
function x = heap_maximum(A)
% 對于最大優先隊列
x = A(1);
end
- 3. 檢索并删除具有最大鍵字的元素
function [index_max, A_t] = heap_extract_max(A)
% 去掉并傳回S中的具有最大關鍵字的元素
[m, n] = size(A);
if n < 1
disp('heap underflow');
end
index_max = A(1);
A(1) = A(n);
A(n) = A(n-1);
A = max_heapify(A,1,n);
A_t = A;
end
- 4. 将元素x的關鍵字值增加到k
function [A] = heap_increase_key(A,i,key)
% 将元素x的關鍵字值增加到k，這裡假設k的值不小于x的原關鍵字值
if key < A(i)
disp('error : new key is smaller than current key');
end
A(i) = key;
while i > 1 && A(parent(i)) < A(i)
A(i) = A(parent(i));
i = parent(i);
end
end
六、參考文獻
- [1] 算法導論(第三版)