一 堆的概念
1 堆在逻辑上是一棵完全二叉树，在物理存储结构采用的是数组
2 满足父亲节点的值大于（小于）左右孩子子节点的值（左右节点大小不必比较），叫做大根堆（小根堆）或者是最大堆（最小堆）
3 堆的基本作用是快速寻找集合中的最值
二 堆的操作（以大堆为例）
2.1 建堆（向下调整）
建堆前：int[] array = { 27,15,19,18,28,34,65,49,25,37 };
**思路：**叶子节点本身可以是视作一个堆的，对于一个根节点而言，只需要满足左右子树是堆就可以了，那么就需要从最后一个非叶子节点开始，依次向下调整，直至到根节点为止，此时的完全二叉树就是一个堆。
代码实现：
public class Heap { //堆底层的数组 public int[] elem; //表示数组中实际存放的数据个数 public int Useside; //提供一个构造方法,对数组进行实例化 public Heap(){ //以十个数据以内为例 this.elem = new int[10]; } public void CreatHeap(int[] array){ //将给定的数据放到elem数组中 for (int i = 0; i < array.length; i++) { elem[i]=array[i]; Useside++; } //根据思路，我们必须从最后一个非叶子节点，也就是最后一个父亲节点开始向下调整 for(int parent = ((Useside-1)-1)/2;parent>=0;parent--){ shiftDown(parent,Useside); } } //向下调整 public void shiftDown(int parent,int len){ int child=2*parent+1; //向下调整的过程中，要保证孩子节点所在的位置要小于数组的有效长度,超过的已经是调整好了的 while(child<len){ //确保有右节点，且找到左右节点中最大值 if(child+1<len&&elem[child]<elem[child+1]){ child++; } if(elem[child]>elem[parent]){ //1.交换parent与child的值 int tmp = elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; //2 向下调整，检查之后的堆是否还是符合大根堆 parent=child; child=2*parent+1; }else{//说明此时的parent所在的堆就是大根堆了 break; } } } }
运行结果：
2.2 添加元素（向上调整）
在建堆的基础之上，假设我们需要添加元素80
**思路：**与向下调整相反，我们要找到新加入节点的位置，并且要和其父亲节点进行比较，如果比父亲节点大，那么需要接着向上比较，直到child调整到根节点位置或者在调节的过程中，已经成为了大根堆。
代码实现:
public void offer(int val){ //如果满了，我们需要进行扩容处理 if(isFull()){ elem=Arrays.copyOf(elem,2*elem.length); } elem[Useside++]=val; //向上调整 shiftUp(Useside-1); } //向上调整 public void shiftUp(int child){ int parent = (child-1)/2; while(parent>=0){ //由于比父亲节点大，此时需要通过向上调整 if(elem[child]>elem[parent]){ int tmp = elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; //还需要向上调整，进行比较 child=parent; parent=(child-1)/2; }else{//说明没有父亲节点大，那么此时还是一个大根堆，不需要向上调整 break; } } } public boolean isFull(){ return Useside==elem.length; }
实现结果：
2.3 删除元素
**思路：**需要先将堆顶元素与堆的最后一个元素进行换位，然后数组的长度减一，最后对根节点这棵树进行向下调整就可以了
代码实现：
//删除元素 public int poll(){ if (isEmpty()){ throw new RuntimeException("数组中没有数据"); } int oldvalue = elem[0]; elem[0]=elem[Useside-1]; elem[Useside-1]=oldvalue; Useside--; shiftDown(0,Useside); return oldvalue; } public boolean isEmpty(){ return Useside==0; }
实现结果：
2.4 建堆的时间复杂度
从粗略而言，建堆的时间复杂度为O（n*logn），实际上建堆的时间复杂度只需要O（n）具体分析：堆的时间复杂度分析
三 堆的应用——优先级队列（PriorityQueue）
在我们java中，优先级队列的实现就是靠堆来实现的，其实关于优先级队列的底层一些方法，其实就是堆的一些添加与删除的方法
四 课后总结
对于堆的理论其实主要理解向上调整以及向下调整两个问题，其他的都还算是比较简单的，对于堆的理论学习，目前就暂时到这里，下篇我们将利用所学的堆的知识去手撕代码。
