预备知识
完全二叉树的定义：
若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第 h 层从右向左连续缺若干结点，这就是完全二叉树
满二叉树特点：
1、深度为k且含有2k-1个结点的二叉树
2、所有节点的度要么为0，要么为2，且所有叶子节点都在最后一层
完全二叉树特点：
1、树中所含n个节点与满二叉树的节点编号一一对应
2、叶子节点只会出现在最后两层，且叶子节点都是靠左对齐
使用数组来实现完全二叉树时有以下规律：
叶子节点个数=floor((n+1)/2) n是元素数量
父节点索引=floor((i-1)/2) i是当前节点索引
左子节点索引=2i+1
堆
堆(heap)，又称为优先队列(priority queue)，堆并不是队列，在队列中，我们可以进行的操作是向队列中添加元素和按照元素进入队列的先后顺序取出元素。而在堆中，我们不是按照元素进入队列的先后顺序，而是按照元素的优先级取出元素
堆通常是一个可以被看做一棵 [完全二叉树] 的数组对象
我们常用的二叉堆就是一颗任意节点的优先级不小于其子节点的完全二叉树
思考：为什么说 堆通常是一个可以被看做一棵 [完全二叉树] 的数组对象
二叉树相较于数组更为复杂，其结构特点决定所需占用内存空间的大小高于数组
优先级可以是大小比较或其他条件下的比较（因为要求元素要参与比较，所以堆中不允许元素为null）
比如常见的大根堆：任意节点的值总是≥子节点的值，小根堆则相反
堆接口的基本设计
int size( ); 元素的数量
boolean isEmpty( ); 是否为空
void clear( ); 清空堆中所有元素
void add(E element); 插入元素
E get( ); 获得堆顶元素
E remove( ); 删除堆顶元素（取出优先级最高的数据）
E replace(E element); 删除堆顶元素的同时插入一个新元素
以大根堆为例
进行各接口的实现解析
add
插入时，我们首先将要插入的数据放在数组的尾部。但是这样破坏了堆的特性，因此我们需要进行调整，保证堆的特性
大根堆形成条件：任意节点的值大于子节点的值，堆顶节点的值最大
1、将插入的节点和父节点进行比较，若插入节点值大于父节点的值（不符合大根堆形成条件）则 他们之间互换位置
2、若插入节点小于父节点的值（符合大根堆形成条件）或已经达到堆顶，则 返回
3、重复执行以上步骤
public void add(E element){
elementNotNullCheck(element);
insureCapacity(size+1);
elements[size++]=elements;
siftUp(size-1);
}
private void siftUp(int index){
E element=elements[index];
//index必须满足有父节点
while(index>0){
//父节点索引Pindex=floor((index-1)/2
int parentIndex=(index-1)>>1;
//若插入节点的值小于父节点的值，符合大根堆构造条件无需交换直接返回
if(compare(elements[parentIndex],element)>=0) break;
//不符合构造条件，节点位置进行互换后继续下一轮循从当前父节点向上重新寻找合适的位置
temp=elements[parentIndex];
elements[parentIndex]=elements[index];
elements[index]=temp;
//重新赋值，进入下一轮循环，继续向上与父节点进行比较
index=parentIndex;
}
}
向上寻找合适位置的过程中，添加节点经过不断地循环上滤在最终找到合适位置时才进行插入，插入节点并不需要每一次都交换位置，之前一直是父节点的在进行位置交换，所以可以进行优化
private void siftUp(int index){
E element=elements[index];
//index必须满足有父节点
while(index>0){
//父节点索引Pindex=floor((index-1)/2
int parentIndex=(index-1)>>2;
//若插入节点的值小于父节点的值，符合大根堆构造条件无需交换直接返回
if(compare(elements[parentIndex],element)>=0) break;
//不符合构造条件，父节点的位置下移至子节点
elements[index]=elements[parentIndex];
//重新赋值已当前父节点为起点作为子节点进入下一轮循环，继续向上与新的父节点进行比较
index=parentIndex;
}
//循环结束直到找到正确的位置
elements[index]=element;
}
remove
删除元素（取出优先级最高的数据），因为取出堆中最大值后必须要保证不影响堆的构造，所以并不只是将堆顶元素直接赋值为null就完事了
大根堆形成条件：任意节点的值大于子节点的值，所以堆顶节点为最大值
1、将最后一个索引节点的值赋给堆顶节点
2、堆顶节点的值与子节点的值进行比较，若堆顶节点值小于子节点的值（不符合大根堆形成条件），则他们之间互换位置
3、重复执行以上步骤
public E remove(){
emptyCheck();
int root=elements[0];
elements[0]=elements[--size];
elements[size]=null;
siftDown(0);
return root;
}
private void siftDown(int index){
int e=elements[index];
//非叶子节点的数量:floor(size/2)
int critical=size>>2;
//最后一个叶子节点的索引 = 非叶子节点的数量
//保证index是非叶子节点
while(index<critical){
//左子节点索引
int childIndex = (index << 1) + 1;
//c右子节点索引:childIndex+1
if(childIndex+1<size){
//选出左右子节点中的最大值
int child=math.max(elements[childIndex],elements[childIndex+1]);
}
//若堆顶节点值大于子节点的值，符合条件，则返回
if(compare(child,e)<=0) break;
//位置互换
// int temp=child;
// child=elements[index];
// elements[index]=temp;
//堆顶节点不断向下寻找合适位置插入的过程中，与子节点不断地进行位置互换
elements[index]=elements[childIndex];
index=childIndex;
}
//最终找到合适位置
elements[index]=e;
}
批量建堆
外部接口调用
public void main(Stirng[] args){
BinaryHeap<Integer> heap = new BinaryHeap<>();
heap.add(2);
heap.add(5);
heap.add(1);
heap.add(3);
int[] data={2,5,1,3}
BinaryHeap<Integer> heap = new BinaryHeap<>(data, new Comparator<Integer>() {
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
}
若想将一段指定的数据添加进堆中，然后取出优先值，怎么实现？
1、一个接一个的进行插入
2、直接将数组扔进堆中，批量建堆（堆化）
heapify
public BinaryHeap(E[] elements, Comparator<E> comparator) {
super(comparator);
if (elements == null || elements.length == 0) {
this.elements = (E[]) new Object[DEFAULT_CAPACITY];
} else {
size = elements.length;
int capacity = Math.max(elements.length, DEFAULT_CAPACITY);
this.elements = (E[]) new Object[capacity];
for (int i = 0; i < elements.length; i++) {
this.elements[i] = elements[i];
}
heapify();
}
}
private void heapify() {
// 自上而下的上滤
// for (int i = 1; i < size; i++) {
// siftUp(i);
// }
// 自下而上的下滤
for (int i = (size >> 1) - 1; i >= 0; i--) {
siftDown(i);
}
}
批量建堆的过程可以叫做堆化，堆化的两种方式：
1、自上而下的上滤，上滤操作（叶子节点与父节点比较）
2、自下而上的下滤，下滤操作（父节点与叶子节点比较）
效率分析：
完全二叉树的叶子节点数量（n/2，n为总节点数量）为总结点的1/2，若采用方式一，则一半的节点（最后一层的叶子节点）需要进行上滤
所以采用方式2 效率相对更高
清空
此处最大堆的结构利用了数组，所以与数组的清空方式一样
public void clear() {
for (int i = 0; i < size; i++) {
elements[i] = null;
}
size = 0;
}
