1.堆的存储方式

由堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来存储堆。

注意：
对于非完全二叉树，则不适合使用顺序的方式进行存储。因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低。
然后针对这种存储方式，要对完全二叉树进行操作的时候，直接取下标即可：
1）如果i为0，则i表示的结点为根节点，否则i的双亲结点为(i-1)/2;
2)如果2i+1小于结点个数个数，则结点的左孩子下标为2i+1,否则没有左孩子；
3）如果2i+2小于结点个数，则结点i的右孩子下标为2i+2,否则没有右孩子。

2.堆的创建

堆的创建：给定一个数组，整理成堆这样的结构（转换完全二叉树并且使用数组来存储，满足下标条件，满足下标关系，还满足堆的条件）

2.1向下调整

向下调整的思路（以大堆为例）：
从待调整的位置出发作为父节点，然后根据下标关系得到他的子树，然后找到他的子树的最大值，然后他的孩子结点指向左右子树的最大值，然后拿他的最大值与父节点的值做比较，若不满足堆的大小，则交换两个元素。

public class Heap {//向下调整是创建堆的一个核心操作//前提条件是当前被调整的左右子树都是堆//方法参数中给出堆表示当前元素有效位置的大小//可以通过arr.length,这个大小是整个大小//index是表示从这个位置开始向下进项调整private void shiftDown(int [] arr ,int size,int index){//调整过程中，从待调整的位置出发//取出该结点的左右子树（通过下标换算的方式）//若当前是大堆，找出左右孩子中较大的值int parent=index;int child=2*parent+1;while(child<size){//需要找到左右子树中较大的值//左右子树下标差1if(child+1<size&&arr[child+1]>arr[child])  {child=child+1;}//当左右子树遍历执行完之后，child就指向左右子树中较大的值//拿父节点和当前较大的结点去比较，看是否满足大堆的要求if(arr[parent]<arr[child]){//不满足大堆的要求，交换两个元素int tmp=arr[parent];arr[parent]=arr[child];arr[child]=tmp;}else{break;}parent=child;child=2*index+1;}}//建堆操作public void createHeap(int [] arr){//基于向下建堆的操作；//从最后一个结点的父节点往前，对于每个下标从后往前向下调整即可//或者最后一个非叶子结点for(int i=(arr.length-1-1)/2;i>=0;i--){shiftDown(arr,arr.length,i);}}
}

2.2向上调整

向上调整的基本思路（大堆为例）：
首先从当前结点出发作为子节点，然后根据下标的关系表达找到他的父节点，如果双亲比孩子大，则满足堆的性质，调整结束，反之，将两个结点进行交换。然后将结点向上移动。

public  static void shiftUp(int [] arr,int size,int index){int child=index;int parent=(child-1)/2;//如果child为0，已经调整到最上面了while(child>0){if(arr[parent]<arr[child]){//不符合大堆要求//交换两个元素int tmp=arr[parent];arr[parent]=arr[child];arr[child]=tmp;}else{break;}child=parent;parent=(child-1)/2;}}

3.堆的操作

3.1元素插入堆

堆的插入总共需要两个步骤：
1）先将元素放在数组末尾（空间不够时可以扩容）
2）然后将新插入的结点进行向上调整，直到满足堆的条件即可。

public  static void shiftUp(int [] arr,int size,int index){int child=index;int parent=(child-1)/2;//如果child为0，已经调整到最上面了while(child>0){if(arr[parent]<arr[child]){//不符合大堆要求//交换两个元素int tmp=arr[parent];arr[parent]=arr[child];arr[child]=tmp;}else{break;}child=parent;parent=(child-1)/2;}}private int [] arr=new int[100];private int size=0;//往堆中插入元素public void offer(int val){if(size>=arr.length) {return ;}arr[size]=val;size++;//把最后的元素进行向上调整shiftDown(arr,size,size-1);}

3.2取堆顶元素

堆顶元素是第一个元素，结果是显然的。

public class Heap{
//获取堆顶元素public Integer peek(){if(size==0){return null;}return arr[0];}}

3.3删除堆顶元素

基本思路：
采用移形换影，拿0号元素（要删除的元素）和最后一个元素交换，然后size–,然后进行向下调整。

//删除元素（一定是删除堆顶元素）public Integer poll(){if(size==0){return null;}//拿0号元素（要删除的元素）和最后一个元素交换//size--//然后向下调整int result=arr[0];//交换0号元素和size-1项元素int tmp=arr[0];arr[0]=arr[size-1];arr[size-1]=tmp;size--;shiftDown(arr,size,0);return result;}