理解堆的操作并实现优先级队列

堆的操作，最主要的就是向调整和向下调整，用这个两个操作来保证堆的性质，最主要的应用有两个。一个是排序算法——堆排序，另一个就是数据结构——优先级队列

什么是堆？

堆其实就是一个完全二叉树，但是它存储在数组里面，利用数组的下标来进行操作结点，数组和堆就是相对应的

性质
最大堆：每个结点都大于或者等于其两个子结点
最小堆：每个结点都小于或者等于其两个子结点

向上调整和向下调整

这两种操作都是为了维护最大堆或者最小堆的的结构
这里倘若是最大堆
向上调整：某个结点的值大于它的父结点，这时应该将父结点与这个结点进行交换，而当前就是父结点
向下调整：某个结点的值小于它的子结点，这时将子结点和当前结点进行交换，当前这个结点就是子结点

向上调整

 public void shiftUp(int child){
        int parent = (child-1)>>1;
        //向上调整到根节点，就不能在调整
        while (parent >= 0) {
            //父结点小于子结点
            if (arr[parent] < arr[child]) {
                swap(parent, child);
                //较小的孩子和双亲后，可能会导致上层不满足小堆的性质
                child = parent;
                parent = (child - 1) >> 1;
            } else {
                return;
            }
        }
    }

向下调整

public void shifDown(int parent){
	//child标记parent子结点中较大的孩子
	int child = parent*2+1;//默认情况下，先标记左孩子，因为可能不存在右孩子
	int len = arr.length;
	while(child < len){
		//判断是否存在右孩子并符合条件
		if(child + 1 < len && arr[child] < arr[child+1]){
			child+=1;
		}
		if(arr[parent] < arr[child]){
			swap(child,parent);
			//交换之后可能会导致其子树不是大堆结构
			parent = child;
			child = parent*2+1;
		}else{
		    return;
		}
	}
}

优先级队列

这种数据结构，当你插入或者删除数据的时候，元素会自动的排序，其底层的原理就是堆的操作。
插入：insert方法就是先将插入的元素放在堆底的最后，然后进行向上调整，让其调整到正确的位置

  boolean insert(int x){
        //将元素插入到数组中
        array[size++] = x;
        //向上调整
        shiftUp(size-1);
        return true;
    }

删除：poll方法就是先将堆顶元素A和堆底的最后一个元素B进行交换，然后删除A，向下调整B,直到调整到正确的位置

 int poll(){
        int ret = arr[0];
        swap(0,size-1);
        size--;
        shifDown(0);
        return ret;
 }

一个优先级队列就实现了，插入和删除的时间复杂度为O(logN)，N为堆的中元素的总数

堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，其实就是一个选择排序（后面的元素已经是有序的，只需要排前面的元素），其时间复杂度为O(nlog n)。
升序（构建大堆），降序（构建小堆）
堆排序的思想：
1、先将待排序的元素，利用向下调整的操作构建一个大顶堆；
2、再利用堆删除的思想将堆顶元素和堆底的最后一个元素进行交换，此时末尾就是最大的元素，但是此时堆结构可能已经破坏，从堆顶开始进行向下调整维护堆的结构，再利用堆删除，如此反复执行，直到所有的元素都是有序的

第一步：构建大堆

第二步：利用堆删除思想，将堆顶元素和堆底的最后一个元素进行交换，此时最后一个元素就是最大的，依次将剩下的元素进行堆的重新构建，如此反复得到的就是一个有序的序列