1.概念：二叉堆是经常被提到的堆， 堆满足： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树
2.分类：堆具体分为大根堆和小根堆。大根堆的父节点一定是比子节点的value大的，小根堆的父节点一定是比子节点的value小的。 父节点和子节点的关系，已知父节点为k,则左孩子为2k+1,右孩子为2k+2，且都应该小于等于总结点个数。根节点从0开始，因为底层是数组。 已知子节点位置为k，则父节点位置为（k-1）/2，向下取整 （以大根堆为例） 向下调整： 整体思想： 从最后一个子树开始调整。如果字节比父节点大，则交换。每一棵树都是向下调整。 3.创建堆
public class Heap { public int []elem;//底层是一个数组 public int usedSize;//存放数据个数 public Heap() { this.elem = new int[10]; } public void creatHeap(int[] arr){ for (int i = 0; i <arr.length; i++) { this.elem[i]=arr[i]; this.usedSize++; } //从最后一个子树开始调整 for (int i = (this.usedSize-1-1)/2; i >=0 ; i--) {//this.usedSize-1代表最后一个节点,(this.usedSize-1-1)/2每颗子树的根节点 adjustDown(i,this.usedSize); } } public void adjustDown(int root,int len){//root代表每个子树的开始位置，len代表的是结束位置。 int parent=root; int child=2*parent+1;//左孩子 while (child<len){//孩子节点的下标一定会小于等总节点的数量-1。 if(child+1<len){ //有右孩子 if (elem[child]<elem[child+1]){//找到左右孩子的最大值，child保存最大孩子的坐标 child=child+1; } } //比较child节点和父节点的值，如果大则交换 if (elem[child]>elem[parent]){ int tmp=elem[child]; elem[child]=elem[parent]; elem[parent]=tmp; parent=child; child=2*parent+1; }else {//如果小则不用交换，说明已经调整好了 break; } } } public void show(){ for (int i = 0; i <this.usedSize ; i++) { System.out.print(elem[i]+" "); } } }最终的堆：
创建堆的时间复杂度：O（n），调整一次堆的时间复杂度O（log n） 4.给堆里插入元素
新增时，在数组尾部增添元素，并且调整堆。向上调整
public void push(int value){ //0.判断是否扩容 if (this.elem.length==this.usedSize){ this.elem= Arrays.copyOf(this.elem,elem.length*2); } elem[this.usedSize]=value; this.usedSize++; adjustUp(this.usedSize-1); } private void adjustUp(int child) { int parent=(child-1)/2; while (child>0){ if (elem[parent]<elem[child]){ int tmp=elem[parent]; elem[parent]=elem[child]; elem[child]=tmp; child=parent; parent=(child-1)/2; }else { break; } } }5.堆删除元素
public void pop(){//每次移除的都是堆的元素 if (this.usedSize==0){//是否为空 return; } int tmp=this.elem[this.usedSize-1]; this.elem[this.usedSize-1]=this.elem[0]; this.elem[0]=tmp; this.usedSize--;//删除这个元素 adjustDown(0,this.usedSize); }