一：堆
1.特点：
* 它是完全二叉树。除了树的最后一层节点不需要是满的，其他的每一层从左到右都是满的。最后一层不允许有"洞"节点
* 常常用一个数组来实现
* 堆中的每一个节点关键字都大于等于这个节点的子节点的关键字
2.模型展示
3.堆的适用场景
堆和二叉搜索树相比是弱序的。
在堆中按序遍历节点是很困难的，因为堆只要求从根到叶子的每一条路径，节点都是按降序排序的即可。
在堆中查找某个节点也是很困难的
但是堆能够快速移除最大节点、快速插入新节点，基于这种特点，可以作为优先级队列来使用
二：堆的操作演示
1.添加节点
初始树
添加节点79（会从树最后一个空着的节点插入，以上树中，由于当前叶节点已满，所以另起一层，从最左边添加节点，作为68的左子节点）
79节点，向上筛选，发现比自己小的父节点则换位，如下
同样，如果上树再添加子节点99，则最终结果为
添加节点总结：
* 将新节点插入到最后一个空着的单元中
* 向上比较这个节点，直到它在一个比它大的之下，一个比它小的之上
2.删除节点
初始树
点击删除，堆会删除最上面一个节点（也是全树最大的一个节点）87
删除完之后，跟节点为空，此时会拿树的最后一个节点（33）补上
然后根节点33逐个向下比较，碰到比自己大的则换位，一直到换不动为止，最后结果如下所示
删除节点步骤总结：
* 移走根
* 把最后一个节点移动到根的位置
* 一直向下筛选这个节点，直到它在一个大于它的节点之下，小于它的节点之上为止
三：堆的源码解析
class Heap {
private Node[] heapArray;
private int maxSize; // size of array
private int currentSize; // number of nodes in array
public Heap(int mx){
maxSize = mx;
currentSize = 0;
heapArray = new Node[maxSize];
}
public boolean isEmpty() {
return currentSize == 0;
}
public boolean insert(int key) {
if (currentSize == maxSize)
return false;
Node newNode = new Node(key);
heapArray[currentSize] = newNode;
trickleUp(currentSize++);
return true;
}
// 删除最大节点（也就是根节点）
public Node remove(){
Node root = heapArray[0];
heapArray[0] = heapArray[--currentSize];
trickleDown(0);
return root;
}
/**
* 向上遍历，发现父节点比当前节点值小，则替换
* 假定当前节点索引为X
* 则父节点索引为(X-1)/2
* 左子节点索引为2*X+1
* 右子节点索引为2*X+2
*
* @param index
*/
public void trickleUp(int index) {
int parent = (index - 1) / 2;
Node bottom = heapArray[index];
while (index > 0 && heapArray[parent].getKey() < bottom.getKey()) {
heapArray[index] = heapArray[parent]; // move it down
index = parent;
parent = (parent - 1) / 2;
}
heapArray[index] = bottom;
}
//向下遍历，发现子节点比自己大则替换
public void trickleDown(int index) {
int largerChild;
Node top = heapArray[index]; // save root
while (index < currentSize / 2) // while node has at
{ // least one child,
int leftChild = 2 * index + 1;
int rightChild = leftChild + 1;
// find larger child
if (rightChild < currentSize && // (rightChild exists?)
heapArray[leftChild].getKey() < heapArray[rightChild].getKey())
largerChild = rightChild;
else
largerChild = leftChild;
// top >= largerChild?
if (top.getKey() >= heapArray[largerChild].getKey())
break;
// shift child up
heapArray[index] = heapArray[largerChild];
index = largerChild; // go down
}
heapArray[index] = top; // root to index
}
public boolean change(int index, int newValue) {
if (index < 0 || index >= currentSize)
return false;
int oldValue = heapArray[index].getKey(); // remember old
heapArray[index].setKey(newValue); // change to new
if (oldValue < newValue) // if raised,
trickleUp(index); // trickle it up
else // if lowered,
trickleDown(index); // trickle it down
return true;
}
}
class Node {
private int iData;
public Node(int key) {
iData = key;
}
public int getKey() {
return iData;
}
public void setKey(int id) {
iData = id;
}
}
