优先级队列（堆）

二叉树的顺序存储

存储方式下标关系 堆

概念基本操作

建堆入队出队获取队头元素 top-K问题堆排序

使用数组保存二叉树结构，方式即将二叉树用层序遍历方式放入数组中。
一般只适合表示完全二叉树，因为非完全二叉树会有空间的浪费。
这种方式的主要用法就是堆的表示。

已知双亲(parent)的下标，则：
左孩子(left)下标 = 2 * parent + 1;
右孩子(right)下标 = 2 * parent + 2;已知孩子（不区分左右）(child)下标，则：
双亲(parent)下标 = (child - 1) / 2;

堆逻辑上是一棵完全二叉树堆物理上是保存在数组中满足任意结点的值都大于其子树中结点的值，叫做大堆，或者大根堆，或者最大堆。反之，则是小堆，或者小根堆，或者最小堆。

 public void creatBigHeap(int[] array) {
    	for(int i=0;i=0;parent--) {
    		//调整
    		shiftDown(parent,usedSize);
    	}
    }
  //parent:每颗树的根节点   len:每颗树调整的结束位置
    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]) {
    			int tmp=elem[child];
    			elem[child]=elem[parent];
    			elem[parent]=tmp;
    			parent=child;
    			child=2*parent+1;
    		}else {
    			break;
    		}
    	}
    }

  //入队列（以大堆为例）
    public void offer(int val) {
    	if(isFull()) {
    		//扩容
    		elem=Arrays.copyOf(elem, elem.length *2);
    		
    	}
    	elem[usedSize]=val;
    	usedSize++;
    	//注意这里传入的是usedSize-1
    	shiftUp(usedSize-1);
    }
    public boolean isFull() {
    	return usedSize==elem.length;
    }

 //向上调整
    public void shiftUp(int child) {
    	int parent=(child-1)/2;
    	while(child >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 int poll() {
    	if(isEmpty()) {
    		throw new RuntimeException("优先级队列为空");
    	}
    	 int tmp=elem[0];
		 elem[0]=elem[usedSize-1];
		 elem[usedSize-1]=tmp;
		 usedSize--;
    	 shiftDown(0,usedSize);
    	 //返回要出队的元素
    	 return tmp;
    }
    public boolean isEmpty() {
    	return usedSize==0;
    }
  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]) {
    			int tmp=elem[child];
    			elem[child]=elem[parent];
    			elem[parent]=tmp;
    			parent=child;
    			child=2*parent+1;
    		}else {
    			break;
    		}
    	}
    }

//获取队头元素
    public int peek() {
    	if(isEmpty()) {
    		throw new RuntimeException("优先级队列为空");
    	}
    	return elem[0];
    }
    

 public void heapSort() {
    	int end=usedSize-1;
    	while(end>0) {
    		 int tmp=elem[0];
    		 elem[0]=elem[end];
    		 elem[end]=tmp;
    		 shiftDown(0,end);
    	     end--;
    	}
    }