堆的删除
注意：堆的删除一定删除的是堆顶元素。具体如下：
1. 将堆顶元素对堆中最后一个元素交换
2. 将堆中有效数据个数减少一个
3. 对堆顶元素进行向下调整
1. public void pollHeap() { 2. if(isEmpty()){ 3. throw new RuntimeException(); 4. } 5. int temp=elem[0]; 6. elem[0]=elem[usedSize-1]; 7. elem[usedSize-1]=temp; 8. usedSize--; 9. //保证依然是大根堆 10. shiftDown(0,usedSize); 11. 12. } 13. 14. public boolean isEmpty() { 15. return usedSize==0; 16. } 17. 18. /** 19. * 20. * @param root 是每棵子树的根节点的下标 21. * @param len 是每棵子树调整结束的结束条件 22. * 向下调整的时间复杂度：O(logn) 23. */ 24. private void shiftDown(int root,int len) { 25. 26. int child=2*root+1; 27. 28. while(child<len){ 29. 30. if(child+1<len&&elem[child]<elem[child+1]){ 31. 32. child++; 33. } 34. 35. if(elem[root]<elem[child]){ 36. int temp=elem[root]; 37. elem[root]=elem[child]; 38. elem[child]=temp; 39. root=child; 40. child=2*root+1; 41. 42. }else { 43. break; 44. } 45. 46. } 47. 48. 49. }
用堆模拟实现优先级队列（完整代码）
1. import java.util.Arrays; 2. 3. public class PriorityQueue { 4. public int[] elem; 5. public int usedSize; 6. 7. public static final int DEFAULT_INIT_USESZIE=10; 8. public PriorityQueue() { 9. elem=new int[DEFAULT_INIT_USESZIE]; 10. } 11. 12. /** 13. * 建堆的时间复杂度：O(n) 14. * 15. * @param array 16. */ 17. public void createHeap(int[] array) { 18. 19. 20. 21. for(int i=0;i<array.length;i++){ 22. elem[i]=array[i]; 23. usedSize++; 24. if(isFull()){ 25. elem= Arrays.copyOf(this.elem,2*this.elem.length); 26. } 27. } 28. for(int parent=(usedSize-1-1)/2;parent>=0;parent--){ 29. 30. shiftDown(parent,usedSize); 31. } 32. 33. } 34. 35. /** 36. * 37. * @param root 是每棵子树的根节点的下标 38. * @param len 是每棵子树调整结束的结束条件 39. * 向下调整的时间复杂度：O(logn) 40. */ 41. private void shiftDown(int root,int len) { 42. 43. int child=2*root+1; 44. 45. while(child<len){ 46. 47. if(child+1<len&&elem[child]<elem[child+1]){ 48. 49. child++; 50. } 51. 52. if(elem[root]<elem[child]){ 53. int temp=elem[root]; 54. elem[root]=elem[child]; 55. elem[child]=temp; 56. root=child; 57. child=2*root+1; 58. 59. }else { 60. break; 61. } 62. 63. } 64. 65. 66. } 67. 68. 69. /** 70. * 入队：仍然要保持是大根堆 71. * @param val 72. */ 73. public void push(int val) { 74. if(isFull()){ 75. elem= Arrays.copyOf(this.elem,2*this.elem.length); 76. } 77. elem[usedSize]=val; 78. usedSize++; 79. shiftUp(usedSize-1); 80. 81. } 82. 83. private void shiftUp(int child) { 84. 85. int parent=(child-1)/2; 86. 87. while(child>0) 88. if(elem[child]>elem[parent]){ 89. 90. int temp=elem[child]; 91. elem[child]=elem[parent]; 92. elem[parent]=temp; 93. child=parent; 94. parent=(child-1)/2; 95. }else{ 96. break; 97. } 98. } 99. 100. public boolean isFull() { 101. return usedSize== elem.length; 102. } 103. 104. /** 105. * 出队【删除】：每次删除的都是优先级高的元素 106. * 仍然要保持是大根堆 107. */ 108. public void pollHeap() { 109. if(isEmpty()){ 110. throw new RuntimeException(); 111. } 112. int temp=elem[0]; 113. elem[0]=elem[usedSize-1]; 114. elem[usedSize-1]=temp; 115. usedSize--; 116. //保证依然是大根堆 117. shiftDown(0,usedSize); 118. 119. } 120. 121. public boolean isEmpty() { 122. return usedSize==0; 123. } 124. 125. /** 126. * 获取堆顶元素 127. * @return 128. */ 129. public int peekHeap() { 130. if(isEmpty()){ 131. return -1; 132. } 133. return elem[0]; 134. } 135. }
常用接口介绍
Java集合框架中提供了PriorityQueue和PriorityBlockingQueue两种类型的优先级队列，PriorityQueue是线程不安全的，PriorityBlockingQueue是线程安全的，本文主要介绍PriorityQueue。
关于PriorityQueue的使用要注意：
1. 使用时必须导入PriorityQueue所在的包，即：
import java.util.PriorityQueue;
2. PriorityQueue中放置的元素必须要能够比较大小，不能插入无法比较大小的对象，否则会抛出
ClassCastException异常
3. 不能插入null对象，否则会抛出NullPointerException
4. 没有容量限制，可以插入任意多个元素，其内部可以自动扩容
5. 插入和删除元素的时间复杂度为
6. PriorityQueue底层使用了堆数据结构, (注意：此处大家可以不用管什么是堆，后文中有介绍)
7. PriorityQueue默认情况下是小堆---即每次获取到的元素都是最小的元素
PriorityQueue常用接口介绍
| 构造器 | 功能介绍 |
| PriorityQueue() | 创建一个空的优先级队列，默认容量是11 |
| PriorityQueue(int initialCapacity) |
创建一个初始容量为initialCapacity的优先级队列，注意： initialCapacity不能小于1，否则会抛IllegalArgumentException异 常 |
| PriorityQueue(Collection<? extends E> c) |
用一个集合来创建优先级队列 |
注意：默认情况下，PriorityQueue队列是小堆，如果需要大堆需要用户提供比较器
1. // 用户自己定义的比较器：直接实现Comparator接口，然后重写该接口中的compare方法即可 2. class IntCmp implements Comparator<Integer>{ 3. @Override 4. public int compare(Integer o1, Integer o2) { 5. return o2-o1; 6. } 7. } 8. public class TestPriorityQueue { 9. public static void main(String[] args) { 10. PriorityQueue<Integer> p = new PriorityQueue<>(new IntCmp());
插入/删除/获取优先级最高的元素
| 函数名 | 功能介绍 |
| boolean offer(E e) |
插入元素e，插入成功返回true，如果e对象为空，抛出NullPointerException异常，时 间复杂度 ，注意：空间不够时候会进行扩容 |
| E peek() | 获取优先级最高的元素，如果优先级队列为空，返回null |
| E poll() | 移除优先级最高的元素并返回，如果优先级队列为空，返回null |
| int size() | 获取有效元素的个数 |
| void clear() |
清空 |
| boolean isEmpty() |
检测优先级队列是否为空，空返回true |
