理解堆的操作并实现优先级队列qq44723296的博客-

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

什么是堆？

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

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

向上调整和向下调整

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

向上调整

 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、再利用堆删除的思想将堆顶元素和堆底的最后一个元素进行交换，此时末尾就是最大的元素，但是此时堆结构可能已经破坏，从堆顶开始进行向下调整维护堆的结构，再利用堆删除，如此反复执行，直到所有的元素都是有序的

第一步：构建大堆

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