[数据结构与算法]优先级队列（堆）

二叉树的顺序存储

存储方式

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

下标关系

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

堆

概念

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

基本操作

建堆

 public void creatBigHeap(int[] array) {
    	for(int i=0;i<array.length;i++) {
    		elem[i]=array[i];
    		 usedSize++;
    	}
    	for(int parent=(usedSize-1-1)/2;parent>=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];
    }
    

top-K问题

堆排序

 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--;
    	}
    }