堆：是用数组实现的完全二叉树，没有使用指针，根据数组的下标进行构建堆
eg：parentIndex = i;—》 leftIndex = 2i+1;rightIndex = 2i+2;
堆的分类：大根堆，小根堆。大根堆的每个子树，根节点是整个树中最大的数据，每个节点的数据都比其子节点大
小根堆的根节点数据是最小的数据，每个节点的数据都比其子节点小
注意：堆的根节点中存放的是最大或者最小元素，但是其他节点的排序顺序是未知的。例如，在一个最大堆中，最大的那一个元素总是位于 index 0 的位置，但是最小的元素则未必是最后一个元素。–唯一能够保证的是最小的元素是一个叶节点，但是不确定是哪一个。
（以小根堆为例 讲解 堆的构建，插入和删除过程）
一，堆的构建
从末尾节点的父节点的这棵树开始调整，根据小根堆的性质，越小的数据往上移动，注意，被调整的节点还有子节点的情况，需要递归进行调整。
2和3交换之后，3所处的节点还有子节点，需要递归检验3所在树是否也符合小根堆的性质
注意：此时9和1发生交换之后，9所处的节点具有子节点，递归调整9所处的树
至此，小根堆构建的过程就完成了，下面看下代码层面的实现
private List<Integer> arr;/** * 构建最小堆，从最后一个节点的父节点开始调整（也可以对数组中某段连续数据即下标从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<arr.size();i++){ buildMinHeap(0,arr.size()-1-i); swap(0,arr.size()-1-i); } }
五，堆和二叉排序树的区别
内存占用：二叉排序树占用的内存空间比我们存储的数据要多，需要分配额外的内存来存储指针指向其左右子节点。堆的实现结构是数据，根据数组具有下标这一特性来执行左/右子节点。
节点的顺序：在二叉排序树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如痴，在小根堆中两个子节点都必须比父节点小，并且左右子节点的数据大小是不确定的。
搜索性能：二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。
飞艇稳赚不赔的打法x,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<arr.size();i++){ buildMinHeap(0,arr.size()-1-i); swap(0,arr.size()-1-i); } }
五，堆和二叉排序树的区别
内存占用：二叉排序树占用的内存空间比我们存储的数据要多，需要分配额外的内存来存储指针指向其左右子节点。堆的实现结构是数据，根据数组具有下标这一特性来执行左/右子节点。
节点的顺序：在二叉排序树中，左子节点必须比父节点小，右子节点必须比父节点大。但是在堆中并非如痴，在小根堆中两个子节点都必须比父节点小，并且左右子节点的数据大小是不确定的。
搜索性能：二叉排序树是为了实现动态查找而涉及的数据结构，它是面向查找操作的，在二叉排序树中查找一个节点的平均时间复杂度是O(logn)；在堆中搜索并不是第一优先级，堆是为了实现排序而实现的一种数据结构，它不是面向查找操作的，因为在堆中查找一个节点需要进行遍历，其平均时间复杂度是O(n)。