堆数据结构简介
堆结构到底是一个什么样的结构？ 想要弄清楚堆是什么，就先要弄清楚堆与树之间的关系。要清楚的一点是堆是树结构中的一种。一个完全二叉树，符合一定的条件时便是堆。一般是因为最大值（完全最大堆）或最小值（完全最小堆）是根元素的树，所以称之为堆，而值得注意的是堆不仅仅有完全堆。只是因为完全堆便于检索故被广泛使用。
堆有称为优先队列，优先队列相信大家都听说过，生活中有很多情况都是优先队列的模型，比如医院的急症，在急症室中，病人看病的顺序并不是普通的队列（先进先出），而是有紧急情况的病人优先获得治疗。
堆的经典实现（二叉堆）： 二叉堆的定义为，最大值（这里指的是最大完全堆，最小完全堆反之）为根节点，其子节点不比父节点大，且每一个节点都必须填满子节点，如果元素不够，从左开始以此向右填满。
- 每一个子节点都不比其父节点大
- 每个节点至多有2个节点
- 每一层都必须填满（假设有n层，那么1~n-1层必须填满）
- 最后一层填不满，从左往右开始放置
二叉堆实现（数组方式）
shiftUp
//返回添加成功与否
public boolean insert(T t) {
if (data.length <= count + 1) {
return false;
}
// 这里需要计算机先count++ 然后再data[count]赋值，故使用++count
data[++count] = t;
shfitUp(count);
return true;
}
/**
* 数组index[count]元素，进行上浮操作
*
* @param k 需要上浮操作的index
*/
private void shfitUp(int k) {
int father;
while (k > 1
&& data[father = k / 2].compareTo(data[k]) < 0) {
CommonUtils.swap(data, k, father);
k = father;
}
}
shiftDown
/**
* 取出heap中最大元素，并删除
*
* @return
*/
public T extractMax() {
if (!isEmpty()) {
if (count == 1) {
return data[count--];
}
T item = data[1];
CommonUtils.swap(data, 1, count--);
shfitDown(1);
return item;
}
return null;
}
/**
* 下浮操作
* 将位于k位置的元素进行下浮操作
*
* @param k
*/
private void shfitDown(int k) {
// int left;
// int right;
// while ((left = 2 * k) < count) {
// if ((right=left+1)<count
// &&data[left].compareTo(data[right])<=0
// &&data[k].compareTo(data[right])<=0){
// CommonUtils.swap(data,right,k);
// k = right;
// }else if (data[right].compareTo(data[left])<=0
// &&data[k].compareTo(data[left])<=0){
// CommonUtils.swap(data,left,k);
// k = left;
// }else {
// break;
// }
// }
/**
* 第二种写法
*/
// j表示，（2*k）与（2*k+1）中值最大的那个
int j;
while ((j = 2 * k) <= count) {
if (j + 1 <= count
&& data[j + 1].compareTo(data[j]) > 0)
j++;
if (data[j].compareTo(data[k]) <= 0) {
break;
}
CommonUtils.swap(data, k, j);
k = j;
}
}
其实这个时候我们就可以做出一个排序算法了，将一个无序的数组一个个的放入堆中，然后再一个个的拿出来，就是一个有序的过程。但是这个效率实在太慢了，其实还有一个跟快的方式，传入一个无序的数组，通过自身的操作，将其数组变成一个堆，这个操作也称之为heapify.
heapify
//构造函数，传入一个数组。
public MaxHeap(T[] arr) {
int length = arr.length;
data = (T[])new Comparable[length+1];
//将数组arr中元素，复制到data中并从index 1开始
System.arraycopy(arr,0,data,1,length);
this.count = length;
heapify();
}
//将此数组heapify为一个堆
private void heapify() {
int k = count/2;
for (int i = k; i > 0; i--) {
shfitDown(i);
}
}
