一、引言
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
注：凡属于本公众号内容，未经允许不得私自转载，否则将依法追究侵权责任。