堆是一种特殊的树，那么堆有什么样的特点呢？
- 堆是一颗完全二叉树
- 堆必须满足其任意节点都要大于等于（或小于等于）其左右子节点（大于等于还是小于等于取决于要构建一个大顶堆还是小顶堆
堆的实现
因为堆是一颗完全二叉树，我们知道完全二叉树是很适合用数组存储的（因为不会有空间浪费）
堆的插入
简单的插入动作会破坏堆的特性，所以我们要在数据插入后，重新根据堆的特性重新调整数组使其重新符合堆的特性，这个过程叫做堆化。
堆化分为自上而下和自下而上，插入一般是自下而上的堆化过程。
以大顶堆为例子，插入的逻辑其实就是在堆的最后（其实就是数组里的第一个空的位置）插入一个元素，然后不停的和父节点比较，如果插入数据大于父节点，则和父节点交换，直到无法交换为止
堆的插入
package tree;
/**
* @author TioSun
*/
public class Heap {
/**
* 数组，从下标1开始存储数据
*/
private int[] a;
/**
* 堆可以存储的最大数据个数
*/
private int capacity;
/**
* 堆中已经存在的数据个数
*/
private int count;
public Heap(int capacity) {
this.a = new int[capacity + 1];
this.capacity = capacity;
this.count = 0;
}
public void insert(int data) {
// 判断是否堆满
if (count >= capacity) {
return;
}
++count;
a[count] = data;
// 表示新插入数据的当前位置
int i = count;
// 自下而上堆化
while (i/2 > 0 && a[i] > a[i/2]) {
int temp = a[i];
a[i] = a[i/2];
a[i/2] = temp;
i = i/2;
}
}
}
删除堆顶元素
删除堆顶元素的一般做法是用最后一个元素去替换堆顶元素，然后自上而下堆化。
以大顶堆为例，自上而下堆化的步骤是将堆顶元素和左右子节点进行比较，如果小于左右子节点中的其中一个节点，则交换，如果小于左右两个子节点，则和左右子节点中的大的那个交换，重复该步骤，直到无法交换
参照下图，删除堆顶元素41的步骤如下
- 将堆顶元素41用29替换
- 将29和27、39比较
- 29和39交换
- 29和33、36比较
- 29和36交换
-
29和26比较，无法交换，堆化结束
大顶堆
package tree;
/**
* @author TioSun
*/
public class Heap {
/**
* 数组，从下标1开始存储数据
*/
private int[] a;
/**
* 堆可以存储的最大数据个数
*/
private int capacity;
/**
* 堆中已经存在的数据个数
*/
private int count;
public Heap(int capacity) {
this.a = new int[capacity + 1];
this.capacity = capacity;
this.count = 0;
}
public void removeTop() {
if (count == 0) {
return;
}
// 将堆顶元素用最后一个元素替换
a[1] = a[count];
count--;
// 表示替换后的数据的当前位置
int i = 1;
while (true) {
// 需要交换的目标位置，先设为当前位置以表示无需交换
int targetIndex = i;
// 尝试和左子节点比较
if (i * 2 < count && a[i] < a[i * 2]) {
// 将交换位置暂定为左子节点
targetIndex = i * 2;
}
// 尝试和右子节点比较
if (i * 2 + 1 < count && a[targetIndex] < a[i * 2 + 1]) {
targetIndex = i * 2 + 1;
}
if (targetIndex == i) {
// 无需交换
break;
}
// 与待交换位置的元素交换
int temp = a[i];
a[i] = a[targetIndex];
a[targetIndex] = temp;
i = targetIndex;
}
}
}
