优先级队列（PriorityQueue）
优先级队列的概念
前面介绍过队列，队列是一种先进先出(FIFO)的数据结构，但有些情况下，操作的数据可能带有优先级，一般出队列时，可能需要优先级高的元素先出队列，该中场景下，使用队列显然不合适。在这种情况下，我们的数据结构应该提供两个最基本的操作，一个是返回最高优先级对象，一个是添加新的对象。这种数据结构就是优先级队列(Priority Queue)
JDK1.8中的PriorityQueue底层使用了堆的数据结构，而堆实际就是在完全二叉树的基础之上进行了一些元素的调整。
堆（Heap）
堆的概念
如果有一个关键码的集合K = {k0，k1， k2，…，kn-1}，把它的所有元素按完全二叉树的顺序存储方式存储 在一个一维数组中，并满足：Ki <= K2i+1 且 Ki<= K2i+2 (Ki >= K2i+1 且 Ki >= K2i+2) i = 0，1，2…，则称为 小堆(或大堆)。将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。
堆的性质
堆中某个节点的值总是不大于或不小于其父节点的值；
堆总是一棵完全二叉树。
堆的存储方式
从堆的概念可知，堆是一棵完全二叉树，因此可以层序的规则采用顺序的方式来高效存储
注意：对于非完全二叉树，则不适合使用顺序方式进行存储，因为为了能够还原二叉树，空间中必须要存储空节点，就会导致空间利用率比较低
堆的创建：
调整方式：
向下调整 是让调整的结点与其孩子节点进行比较
向上调整 是让调整的结点与其父亲结点进行比较
已知双亲的下标，则左孩子的下标为：left=2parent+1；
则右孩子的下标为：left=2parent+2；
已知孩子结点（不区分左右）的下标，则双亲的下标为：（child-1）/2
大根堆实现代码：
1. public class TestHeap { 2. 3. public int[]elem; 4. public int usedSize; 5. 6. public static final int DEFAULT_SIZE=10; 7. 8. public TestHeap() { 9. elem=new int[DEFAULT_SIZE]; 10. } 11. 12. public void initElem(int[]arr){ 13. 14. for(int i=0;i<arr.length;i++){ 15. elem[i]=arr[i]; 16. usedSize++; 17. } 18. 19. } 20. 21. public void creatHeap(){ 22. //对所有子树的进行判断 23. for(int parent=(usedSize-1-1)/2;parent>=0;parent--){ 24. //进行调整 25. shiftDown(parent,usedSize); 26. } 27. 28. } 29. 30. /** 31. * 32. * @param root 每颗子树的根 33. * @param len 每颗子树结束的位置 34. */ 35. 36. public void shiftDown(int root,int len){ 37. int child=2*root+1; 38. //保证有左孩子 39. while (child<len){ 40. if(child+1<len&&elem[child]<elem[child+1]){ 41. //特别注意这个判断的条件（保证有右孩子才能执行下面的操作） 42. 43. child++;//右移 44. } 45. //现在child下标一定是左右孩子的最大值的下标 46. 47. //判断root下标的值和孩子的最大值 48. if(elem[child]>elem[root]){ 49. int temp=elem[child]; 50. elem[child]=elem[root]; 51. elem[root]=temp; 52. root=child; 53. child=2*root+1; 54. }else{ 55. break; 56. } 57. 58. } 59. 60. 61. } 62. }
小根堆实现代码：
1. public class TestHeap { 2. 3. public int[]elem; 4. public int usedSize; 5. 6. public static final int DEFAULT_SIZE=10; 7. 8. public TestHeap() { 9. elem=new int[DEFAULT_SIZE]; 10. } 11. 12. public void initElem(int[]arr){ 13. 14. for(int i=0;i<arr.length;i++){ 15. elem[i]=arr[i]; 16. usedSize++; 17. } 18. 19. } 20. 21. public void creatHeap(){ 22. //对所有子树的进行判断 23. for(int parent=(usedSize-1-1)/2;parent>=0;parent--){ 24. //进行调整 25. shiftDown(parent,usedSize); 26. } 27. 28. } 29. 30. /** 31. * 32. * @param root 每颗子树的根 33. * @param len 每颗子树结束的位置 34. */ 35. 36. public void shiftDown(int root,int len){ 37. int child=2*root+1; 38. //保证有左孩子 39. while (child<len){ 40. // if(child+1<len&&elem[child]<elem[child+1]){ 41. // //特别注意这个判断的条件（保证有右孩子才能执行下面的操作） 42. // 43. // child++;//右移 44. // } 45. //现在child下标一定是左右孩子的最大值的下标 46. 47. if(child+1<len&&elem[child]>elem[child+1]){ 48. //特别注意这个判断的条件（保证有右孩子才能执行下面的操作） 49. 50. child++;//右移 51. } 52. //现在child下标一定是左右孩子的最小值的下标 53. 54. //判断root下标的值和孩子的最大值 55. // if(elem[child]>elem[root]){ 56. // int temp=elem[child]; 57. // elem[child]=elem[root]; 58. // elem[root]=temp; 59. // root=child; 60. // child=2*root+1; 61. // }else{ 62. // break; 63. // } 64. 65. //判断root下标的值和孩子的最小值 66. if(elem[child]<elem[root]){ 67. int temp=elem[child]; 68. elem[child]=elem[root]; 69. elem[root]=temp; 70. root=child; 71. child=2*root+1; 72. }else{ 73. break; 74. } 75. 76. } 77. 78. 79. } 80. }
建堆的时间复杂度
因为堆是完全二叉树，而满二叉树也是完全二叉树，此处为了简化使用满二叉树来证明(时间复杂度本来看的就是近似值，多几个节点不影响最终结果)：
因此：建堆的时间复杂度为O(N)
堆的插入与删除
堆的插入
堆的插入总共需要两个步骤：
1. 先将元素放入到底层空间中(注意：空间不够时需要扩容)
2. 将最后新插入的节点向上调整，直到满足堆的性质
1. /** 2. * 入队：仍然要保持是大根堆 3. * @param val 4. */ 5. public void push(int val) { 6. if(isFull()){ 7. elem= Arrays.copyOf(this.elem,2*this.elem.length); 8. } 9. elem[usedSize]=val; 10. usedSize++; 11. shiftUp(usedSize-1); 12. 13. } 14. 15. private void shiftUp(int child) { 16. 17. int parent=(child-1)/2; 18. 19. while(child>0) 20. if(elem[child]>elem[parent]){ 21. 22. int temp=elem[child]; 23. elem[child]=elem[parent]; 24. elem[parent]=temp; 25. child=parent; 26. parent=(child-1)/2; 27. }else{ 28. break; 29. } 30. }
