共计 2420 个字符，预计需要花费 7 分钟才能阅读完成。
定义
堆是一种特别的树状结构，我们首先来看看维基百科的上定义。
堆（英语：Heap）是计算机科学中的一种特别的树状数据结构。若是满足以下特性，即可称为堆：“给定堆中任意节点 P 和 C，若 P 是 C 的母节点，那么 P 的值会小于等于（或大于等于）C 的值”。若母节点的值恒小于等于子节点的值，此堆称为最小堆（min heap）；反之，若母节点的值恒大于等于子节点的值，此堆称为最大堆（max heap）。在堆中最顶端的那一个节点，称作根节点（root node），根节点本身没有母节点（parent node）。
总结来说，堆是一个完全二叉树，最多只有两个子节点，并且必须保证根节点是最大的值或者最小的值，所以对于一个堆而言，根节点是最大的值或者是最小的值。
存储
因为堆是一棵完全二叉树，所以使用数组可以高效的存储数据。对于使用数组存储的方式，有两个性质非常关键，对于一个非根节点的节点 i 来说，如果它的下标为 k，那么它的父节点的下标为 (k -1)/2，子节点的下标为 2 *k + 1 和 2 *k + 2
基本操作
堆化
插入
删除
堆化
对于任意一个无序数组而言，实现堆化的步骤如下，我们以构建一个最大堆为例：
找到第一个非叶子节点，对这个节点的左子树和右子树与节点比较，将大的元素放置到父节点的位置，直到父节点已经是最大值或者改节点已经是叶子节点。
依次对所有的非叶子节点进行第一步的操作
private Heap(int[] data)
{
int last_p = data.length – 1;
// i 是第一个非叶子节点
for (int i = (last_p – 1) / 2; i >= 0; i–)
{
heapify(data, i, last_p);
}
this.data = data;
}
private void heapify(int[] data, int start, int end)
{
int value = data[start];
int current_p = start;
// 左孩子
int left_p = 2 * current_p + 1;
while (left_p <= end)
{
// 右节点大于左节点
if (left_p < end && data[left_p] < data[left_p + 1])
{
// 移动位置到右节点
left_p++;
}
// 当前的父节点已经是最大值
if (data[left_p] < value)
{
break;
}
else
{// 子节点上移到父节点的位置
data[current_p] = data[left_p];
current_p = left_p;
left_p = current_p * 2 + 1;
}
}
data[current_p] = value;
}
插入
插入的算法如下：. 将新增的节点放在数组的最末端，也就是数组的最后一个位置。然后计算出父节点的位置，让当前节点与父节点比较，如果父节点比较小，交换位置。重复上述步骤，直到父节点大于当前节点或者当前节点是根节点。
public int insert(int value)
{
checkSize();
int position = data.length – 1;
data[position] = value;
int current_p = position;
int parent_p = (position – 1) / 2;
while (current_p > 0)
{
if (data[parent_p] > value)
{
break;
}
else
{
data[current_p] = data[parent_p];
current_p = parent_p;
parent_p = (current_p – 1) / 2;
}
}
data[current_p] = value;
return position;
}
删除
删除的算法如下：将数组最后一个节点与当前需要删除的节点替换，删除最后一个节点，对于替换的节点来说，相当于进行了依次插入操作，不过这次是从上往下的插入。算法与 remove 相同，也是比较最大的值进行替换，直到不满足条件为止。
删除根节点
public int remove()
{
int root = data[0];
int last = data[data.length – 1];
data[0] = last;
data = Arrays.copyOf(data, data.length – 1);
if (data.length == 0)
{
return root;
}
// 从顶点开始调整
int current_p = 0;
int l = current_p * 2 + 1;
int value = data[current_p];
while (l < data.length)
{
if (l < data.length – 1 && data[l] < data[l + 1])
{
l++; // 右孩子大
}
if (data[l] <= value)
{
break;
}
else
{
data[current_p] = data[l];
current_p = l;
l = current_p * 2 + 1;
}
}
data[current_p] = value;
return root;
}
应用
堆应用比较多的一个用处就是堆排序，对于一个数组进行堆化之后，第一个数组是最大的值，然后交换第一个数和最后一个数，这样最大的数就落在了最后一个数组的位置。缩小数组，重复之前的步骤，最后就得到了一个排序好的数组。
int[] data = new int[] {20, 40, 80, 33, 111, 47, 21, 90, -1};
HeapSort hs = new HeapSort();
hs.heap_array(data, data.length – 1);
for (int i = 0; i < data.length – 1; i++)
{
int tmp = data[0];
data[0] = data[data.length – 1 – i];
data[data.length – 1 – i] = tmp;
hs.heap_array(data, data.length – 2 – i);
}
System.out.println(Arrays.toString(data));
代码地址：https://gitee.com/devnew/Algo…
