堆：是用数组实现的完全二叉树，没有使用指针，根据数组的下标进行构建堆
eg：parentIndex = i;—》 leftIndex = 2i+1;rightIndex = 2i+2;
堆的分类：大根堆，小根堆。大根堆的每个子树，根节点是整个树中最大的数据，每个节点的数据都比其子节点大
小根堆的根节点数据是最小的数据，每个节点的数据都比其子节点小
注意：堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
（以小根堆为例 讲解 堆的构建，插入和删除过程）
一，堆的构建
从末尾节点的父节点的这棵树开始调整，根据小根堆的性质，越小的数据往上移动，注意，被调整的节点还有子节点的情况，需要递归进行调整。
2和3交换之后，3所处的节点还有子节点，需要递归检验3所在树是否也符合小根堆的性质
注意：此时9和1发生交换之后，9所处的节点具有子节点，递归调整9所处的树
至此，小根堆构建的过程就完成了，下面看下代码层面的实现
private List
/**
* 构建最小堆，从最后一个节点的父节点开始调整（也可以对数组中某段连续数据即下标从firstIndex -> endIndex进行建堆）
* @param firstIndex 起始下标
* @param enIndex 结束下标
*/
public void buildMinHeap(int firstIndex,int enIndex) {
for (int i = enIndex/2; i >= firstIndex; i--) {
adjustDown(i,enIndex);
}
}
/**
* 调整当前子树，越小的数据往上移动，注意调整的该节点还有子节点的情况，所以需要递归调整。
* @param parentIndex 父节点的下标
*/
private void adjustDown(int parentIndex,int endIndex) {
int left = 2 * parentIndex + 1;
int right = 2 * parentIndex + 2;
//最小值的下标
int minIndex = parentIndex;
if (left < endIndex && arr.get(left) < arr.get(minIndex)) {
minIndex = left;
}
if (right < endIndex && arr.get(right) < arr.get(minIndex)) {
minIndex = right;
}
if(minIndex == parentIndex){
return;
}
//交换元素
swap(parentIndex,minIndex);
//递归调整
adjustDown(minIndex,endIndex);
}
private void swap(int parentIndex,int minIndex){
int temp = arr.get(parentIndex);
arr.set(parentIndex,arr.get(minIndex));
arr.set(minIndex,temp);
}
二、插入
新增元素首先插入在堆的末尾元素，然后依据小根堆的性质，自底向上，递归调整。
以上面构建的小根堆为例，新插入元素0。
1，首先在堆的末尾插入新增元素
2，自底向上，递归调整其父节点
（插入是在小根堆构建完成的基础上进行的操作，所以在交换之后其子节点所在的树也都是小根堆，所以不需要再进行递归调整）
代码实现：
/**
* @param item 要插入的元素
*/
public void insertToMinHeap(int item){
arr.add(item);
//根节点
if(arr.size() == 1){
return;
}
adjustUp(arr.size()-1);
}
/**
* 向上调整
* @param childIndex 要往上调整的子节点的下标
*/
private void adjustUp(int childIndex){
int parentIndex = (childIndex - 1)/2;
int parentItem = arr.get(parentIndex);
int childItem = arr.get(childIndex);
if(parentItem > childItem){
swap(parentIndex,childIndex);
adjustUp(parentIndex);
}
}
三、堆删除
对于最大堆和最小堆，删除操作是针对堆顶元素而言的，即把末尾元素移动到堆顶，再自定向下(重复构建堆的操作)，递归调整。
1，将末尾元素移动到堆顶
此时所有的子树都符合小根堆的性质了，即完成堆调整。
代码实现：
public int deleteMinHeap(){
//取出最小元素，并将最后一个元素置顶
int minItem = arr.get(0);
arr.set(0,arr.get(arr.size()-1));
//移除末尾元素
if(arr.size() > 1){
arr.remove(arr.size() - 1);
}
//向下调整堆(该实现见上面)
adjustDown(0,arr.size()-1);
return minItem;
}
四、堆排序：（升序–》大根堆，降序–》小根堆）
利用大根堆/小根堆的特性（以小根堆为例），第一次建完小根堆之后，最小的元素将位于0号下标，将0号元素和最后一个元素交换，然后再将剩下的树再建小根堆，循环进行此操作直到完成所有数据
1，将无序数组构建成小根堆
2，将堆顶元素和末尾元素交换位置，使最小元素落在末尾
3，除了2步骤落到末尾的元素，对剩下的元素继续建小根堆(重复1，2的动作)，直到完成所有的元素即完成排序
代码实现：
/**
* 先建成最小堆，再将堆顶元素和堆尾元素交换，除了当前堆的堆尾元素，对剩下的元素再次进行建堆
*/
public void heapSort(){
for(int i = 0;i buildMinHeap(0,arr.size()-1-i); swap(0,arr.size()-1-i); } } 五，堆和二叉排序树的区别 内存占用：二叉排序树占用的内存空间比我们存储的数据要多，需要分配额外的内存来存储指针指向其左右子节点。堆的实现结构是数据，根据数组具有下标这一特性来执行左/右子节点。 节点的顺序：在二叉排序树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如痴，在小根堆中两个子节点都必须比父节点小，并且左右子节点的数据大小是不确定的。 搜索性能：二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。